回溯法求解子集和数问题

1、子集和数问题

代码（仅供参考）：

#include
#include 
#include
using namespace std;
int M = 0;
int n = 0;
float W[100];
bool X[100] = {};
int flag = 0;void SumSubSet(float s, int k, float r)
{float sum = 0;X[k] = 1; if (s + W[k] == M){flag++;for (int i = 0; i <= k; i++){printf("X[%d}==%d\t", i, X[i]);}printf("\n");for(int i = 0; i <= k; i++){if (X[i] == 1){printf("W[%d]==%.0f\t", i, W[i]);sum += W[i];}               }sum = 0;printf("\n**************************************************\n\n");}else if (s + W[k]+W[k+1]<=M){SumSubSet(s + W[k], k + 1, r - W[k]);}if (s + r - W[k] >= M && s + W[k + 1] <= M){X[k] = 0; //生成右子树SumSubSet(s, k + 1, r - W[k]);}
}int main()
{int k=0;float r;float s = 0;cout << "请输入总和M：" <<endl;cin >> M;cout << "请输入子集元素个数n：" <<endl;cin >> n;cout << "请输入子集元素：" <<endl;for (int i = 0; i <n; i++){cin >> W[i];}for (int i = 0; i <n; i++){r += W[i];}cout<<endl;cout << "采用回溯算法求解该定和子集问题：" <<endl;SumSubSet(s, k, r);cout <<"综上所述，共有"<<flag<<"种方案"<<endl;return 0;
}

运行结果示例：

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！