动态规划四.0-1背包问题

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 #define maxi 81
 5 #define maxj 81
 6 
 7 void knapsack(int n,int W,int *w,int *v,int c[][maxj])
 8 {
 9 /*    for(int i=0;i<=W;i++)
10     c[0][i]=0;*/
11     for(int i=1;i<=n;i++)
12     {
13     //    c[i][0]=0;
14         for(int k=1;k<=W;k++)
15         {
16             if(w[i]<=k)
17             {
18                 if(c[i-1][k]<v[i]+c[i-1][k-w[i]])
19                 c[i][k]=v[i]+c[i-1][k-w[i]];
20                 else c[i][k]=c[i-1][k];
21             }
22             else c[i][k]=c[i-1][k];
23         }
24     }
25 }
26 
27 void output(int n,int W,int c[][maxj],int *w)
28 {
29     int x[n],t=W;
30     memset(x,0,sizeof(x));
31     for(int i=n;i>0;i--)
32     {
33         if(c[i][W]==c[i-1][W])
34         x[i]=0;
35         else 
36         {
37             x[i]=1;
38             W-=w[i];
39         }
40     }
41     
42     //如果 c[i][W]==c[i-1][W]，表示当前物品并未放入背包，从c[i-1][W]继续构造最优解，否则从c[i-1][W-w[i]]继续构造最优解； 
43     for(int i=1;i<=n;i++)
44     {
45         if(x[i]==1)
46         cout<<i<<" ";
47     }
48     cout<<c[n][t];
49     cout<<endl;
50 }
51 
52 int main()
53 {
54     int n,W,w[maxi],v[maxi];//w是权重，v是价值
55     int c[maxi][maxj]; //当前位置的最大价值和   
56     cin>>n>>W;    //n代表物品的种类，W代表背包总容量
57     memset(c,0,sizeof(c));
58     
59     for(int i=1;i<=n;i++)
60     cin>>w[i]>>v[i];
61     
62     knapsack(n,W,w,v,c);
63     
64     for(int i=0;i<=n;i++)
65     {
66         for(int j=0;j<=W;j++)
67         cout<<c[i][j]<<" ";
68         cout<<endl;
69     }
70     
71     output(n,W,c,w);
72     return 0; 
73  }
动态规划 四.0-1背包问题

动态规划四.0-1背包问题
