01背包带路径

输出背包中选中的物品

方法一，用path[i][j] 到第i个物品体积为j时的状态是否由放入第i个物品转换而来

 1 #include<iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int dp[10005];
 6 bool path[105][10005];
 7 int v[1005],w[10005];
 8 
 9 int main(){
10     int N,V;
11     while(cin>>N>>V){
12         memset(path,0,sizeof(path));
13         memset(dp,0,sizeof(dp));
14         for(int i=1;i<=N;i++)cin>>v[i]>>w[i];
15         for(int i=N;i>=1;i--){
16             for(int j=V;j>=v[i];j--){
17                 if(dp[j] < dp[j-v[i]] + w[i]){
18                     dp[j] = dp[j-v[i]] + w[i];
19                     path[i][j] = 1;
20                 }
21             }
22         }
23         cout<<dp[V]<<endl;
24         for(int i=1,j=V;i<=N&&j>0;i++){
25             if(path[i][j]) {
26                 printf("%d ", i);
27                 j -= v[i];
28             }
29         }
30         cout<<endl;
31     }
32     return 0;
33 }

方法二，定义结构体，对每次加入物品时更新path

 1 #include<iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define MAXN 100005
 6 
 7 int n,V;
 8 struct Node{
 9     int w;
10     string path;
11     void init(){
12         string str(n,'0');
13         w = 0;
14         path = str;
15     }
16 }dp[MAXN];
17 
18 int v[MAXN];
19 int w[MAXN];
20 
21 int main(){
22     while(cin>>n>>V){
23         for(int i=1;i<=n;i++){
24             cin>>v[i]>>w[i];
25         }
26         for(int i=0;i<=V;i++){
27             dp[i].init();
28         }
29         for(int i=1;i<=n;i++){
30             for(int j=V;j>=v[i];j--){
31                 if(dp[j].w <dp[j-v[i]].w + w[i]){
32                     dp[j].w = dp[j-v[i]].w + w[i];
33                     dp[j].path = dp[j-v[i]].path;
34                     dp[j].path[i-1]='1';
35                 }
36             }
37         }
38         cout<<dp[V].w<<endl;
39         cout<<dp[V].path<<endl;
40     }
41     return 0;
42 }