C++回溯法我的代码是没有回溯吗?为什么出来的不是46或者226?而且还段错误?
题目是回溯法的子集和问题
代码:
#include<iostream>
using namespace std;
int a[1001];
int b[1001];
int x[1001];
int nsum;
int n, c;
int k;
void subsetsum(int t){
if( t > n ){
if(nsum == c){
k = 1;
return;
}
}
else {
if(nsum + a[t] <= c) {
nsum += a[t];
x[t] = 1;
subsetsum(t + 1) ;
nsum -= a[t];
}
if(nsum + a[t] > c){
x[t] = 0;
subsetsum(t+1) ;
}
}
}
int main(){
cin >> n >> c;
for(int i=1; i<=n; i++){
cin >> a[i];
b[i] = a[i];
}
subsetsum(1);
if(k == 1){
for(int i=1; i<=n; i++){
if(x[i] == 1) cout << b[i] << " ";
}
}
else cout << "No Solution!" << endl;
return 0;
}
v[j]=1;backtrack(i+1,total+c[i][j]);v[j]=0;//这一步是什么意思啊?v[j]的作用应该是记录第j个工作是否被分配。v[j]=0代表它没被分配。您这个题目最好使用动态规划来求解,可以参见背包问题。