这是子集和问题的解决方案。它使用回溯。我已经考虑了两个多小时了,我就是无法理解。
编辑:根据我的理解,我在代码中添加了一些注释。如果我错了,请纠正我。
#include <iostream>
int n, d, w[10], x[10], count=0;
void subset(int cs, int k, int r)//i dont understand the purpose of cs or of the array x[]
{
int i;
x[k] = 1;
if(cs + w[k] == d) //if the first element is equivalent to the sum that is required
{
std::cout<< "\n\nSolution " << ++count << " is:";
for(i=0; i<=k; i++) // so if the subset criteria are met then the array is printed.
if(x[i] == 1)
std::cout << w[i] << " ";
}
else if(cs + w[k] + w[k+1] <= d) //if the node is promising then go to the next node and
subset(cs + w[k], k+1, r - w[k]); //check if subset criteria are met
if(cs + w[k+1] <= d && cs + r - w[k] >= d) //else backtrack
{
x[k] = 0;
subset(cs, k+1, r-w[k]);
}
}
int main()
{
int sum=0, i;
std::cout << "enter n\n";
std::cin >> n;
std::cout < <"enter " << n << " elements\n";
for(i=0; i<n; i++)
std::cin >> w[i];
for(i=0; i<n; i++)
sum += w[i];
std::cout << "enter value of sum\n";
std::cin >> d;
if(sum < d)
std::cout<<"INVALID SOLUTION\n";
else
subset(0,0,sum);
}
注意:这是一个有效的解决方案。它在使用 g++ 编译时工作。如果这看起来太令人讨厌,我很抱歉,但我只是从代码中不太了解,因此我无法给出太多解释。