无限循环子集和回溯

Question

我正在尝试使用回溯来实现我自己版本的子集和问题，以获得从元素数组中获得给定和的所有可能的解决方案。目前，我的输出被困在无穷大中，输出加起来就是我想要的和，但它超过了数组中可用类型的元素数量。我不知道为什么会发生这种情况，因为我设置了一些停止条件。代码：

#include <stdio.h>
#define MAX 1024
int coins_array[] = {1,1,1,1,1,3,3,3,3,3,3,3,3,3,3,10,10,10,10,10,15,15,15,15,15,15};
int N = sizeof(coins_array) / sizeof(coins_array[0]);
int S = 27, Sol[MAX], sum, sol;
int acceptable(int step)
{
int i = 0, sum = 0;
for(i = 1; i <= step; i++)
{
sum += Sol[i];
}
if((sum <= S) && (step <= N))
return 1;
return 0;
}
int solution(int sum)
{
if (sum == S)
return 1;
return 0;
}
void print_solution(int step)
{
int i;
for(i = 1 ; i <= step ; ++i)
printf("%d ",Sol[i]);
printf("n");
}
void back(int step)
{
int i;
for(i = 0; i < N; i++)
{
Sol[step] = coins_array[i];
sum += coins_array[i];
if(acceptable(step) == 1)
{
if(solution(sum) == 1)
{
print_solution(step);
}
else
back(step+1);
}
sum -= coins_array[i];
}
}
int main()
{
back(1);
return 0;
}

Output (in an infinite loop):
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 

因此，这些数字加起来就是所需的总和，但它超过了可用的1的数量，并且没有使用10或15。我在调试器中遇到了这个问题，我认为循环的问题在back(step+1)。你知道我该怎么解决吗？

Answer 1

不确定这是否涵盖了代码中的所有问题，但至少有一个bug需要修复。

您当前的代码多次使用同一枚硬币。例如，如果将目标设置为2(即S = 2(，则代码将生成一个使用两次coins_array[0]的解决方案。

发生这种情况是因为back函数总是从索引0开始查看coins_array。

void back(int step)
{
int i;
for(i = 0; i < N; i++)
^^^^^
Always starting from zero is wrong

相反，您需要从"；下一个未使用的"；硬币不幸的是，您当前的代码没有跟踪到这一点，因此您需要重新设计您的解决方案。

为了显示上述问题，我对您的程序进行了一些小的更改-1(减少了可用的硬币2(更改了目标值3(添加了一个数组来跟踪使用了哪个硬币(也称为索引(4(打印了索引

因此，通过这些更改，您的代码看起来像：

#define MAX 1024
int coins_array[] = {1,1,3};
int N = sizeof(coins_array) / sizeof(coins_array[0]);
int S = 2, Sol[MAX], IndexUsed[MAX], sum, sol;
int acceptable(int step)
{
int i = 0, sum = 0;
for(i = 1; i <= step; i++)
{
sum += Sol[i];
}
if((sum <= S) && (step <= N))
return 1;
return 0;
}
int solution(int sum)
{
if (sum == S)
return 1;
return 0;
}
void print_solution(int step)
{
int i;
for(i = 1 ; i <= step ; ++i)
printf("%d (%d) ",Sol[i], IndexUsed[i]);
printf("n");
}
void back(int step)
{
int i;
for(i = 0; i < N; i++)
{
Sol[step] = coins_array[i];
IndexUsed[step] = i; 
sum += coins_array[i];
if(acceptable(step) == 1)
{
if(solution(sum) == 1)
{
print_solution(step);
}
else
back(step+1);
}
sum -= coins_array[i];
}
}
int main()
{
back(1);
return 0;
}

并生成输出(添加了我的评论(：

1 (0) 1 (0)  // Illegal - coin at index 0 used twice
1 (0) 1 (1)  // Legal   - coin at index 0 and 1 used to reach the sum 2
1 (1) 1 (0)  // Illegal - this combination have already been used 
1 (1) 1 (1)  // Illegal - coin at index 1 used twice 

正如您所看到的，您的代码打印了4个解决方案，但应该只打印了1个。如前所述，发生这种情况是因为您的代码总是从函数back中的索引零开始