简单的01背包 保存下方案总数 其实就是dp[v]值 输出路径dfs一下
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 using namespace std; 7 int dp[100010],w[110],path[110],o,f[110],n; 8 void dfs(int sw,int v) 9 { 10 int j; 11 if(sw==0) 12 { 13 o = v; 14 return ; 15 } 16 for(j = 1; j <= n ; j++) 17 if(!f[j]&&dp[sw-w[j]]) 18 { 19 path[v] = j; 20 f[j] = 1; 21 dfs(sw-w[j],v+1); 22 f[j] = 0; 23 } 24 } 25 int main() 26 { 27 int i,j,tw; 28 cin>>tw; 29 cin>>n; 30 for(i = 1; i <= n ; i++) 31 cin>>w[i]; 32 dp[0] = 1; 33 for(i = 1 ; i <= n ;i++) 34 for(j = tw ; j>=w[i] ; j--) 35 { 36 dp[j] += dp[j-w[i]]; 37 } 38 int sw = tw; 39 if(dp[tw]==0) 40 cout<<"0 "; 41 else if(dp[tw]>1) 42 cout<<"-1 "<<endl; 43 else 44 { 45 dfs(sw,1); 46 memset(f,0,sizeof(f)); 47 int kk=0; 48 for(i = 1; i < o ; i++) 49 f[path[i]] = 1; 50 for(i = 1; i <= n ;i++) 51 { 52 if(!f[i]) 53 { 54 if(kk) 55 cout<<" "; 56 cout<<i; 57 kk++; 58 } 59 } 60 puts(""); 61 } 62 return 0; 63 }