01背包问题

 1 #include <iostream>  
 2 #include <cstring>  
 3 using namespace std;  
 4 const int N=15;  
 5 int main()  
 6 {  
 7     int v[N]={0,8,10,6,3,7,2};  
 8     int w[N]={0,4,6,2,2,5,1};  
 9     int m[N][N];  
10     int n=6,c=12;  
11     memset(m,0,sizeof(m));  
12     for(int i=1;i<=n;i++)  
13     {  
14         for(int j=1;j<=c;j++)  
15         {  
16             if(j>=w[i])  
17                 m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);  
18             else  
19                 m[i][j]=m[i-1][j];  
20         }  
21     }  
22     for(int i=1;i<=n;i++)  
23     {  
24         for(int j=1;j<=c;j++)  
25         {  
26             cout<<m[i][j]<<' ';  
27         }  
28         cout<<endl;  
29     }  
30     return 0;  
31 }

这一段代码很简单的把01背包问题最后的最大值答案求出，下面这个函数用来从后往前求最优解

 1 void traceback()
 2 {
 3     for (int i = n; i>1; i--)
 4     {
 5         if (m[i][c] == m[i - 1][c])
 6             x[i] = 0;
 7         else
 8         {
 9             x[i] = 1;
10             c -= w[i];
11         }
12     }
13     x[1] = (m[1][c]>0) ? 1 : 0;
14 }

完整代码如下:

 1 #include <iostream>  
 2 #include<windows.h>
 3 using namespace std;
 4 const int N = 15;
 5 int v[N] = { 0,8,10,6,3,7,2 };
 6 int w[N] = { 0,4,6,2,2,5,1 };
 7 int x[N];
 8 int m[N][N];
 9 int n = 6, c = 12;
10 void traceback()
11 {
12     for (int i = n; i>1; i--)
13     {
14         if (m[i][c] == m[i - 1][c])
15             x[i] = 0;
16         else
17         {
18             x[i] = 1;
19             c -= w[i];
20         }
21     }
22     x[1] = (m[1][c]>0) ? 1 : 0;
23 }
24 
25 int main()
26 {
27     
28     memset(m, 0, sizeof(m));
29     for (int i = 1; i <= n; i++)
30     {
31         for (int j = 1; j <= c; j++)
32         {
33             if (j >= w[i])
34                 m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i]);
35             else
36                 m[i][j] = m[i - 1][j];
37         }
38     }
39 
40     for (int i = 1; i <= n; i++)
41     {
42         for (int j = 1; j <= c; j++)
43         {
44             cout << m[i][j] << ' ';
45         }
46         cout << endl;
47     }
48     traceback();
49     for (int i = 1; i <= n; i++)
50         cout << x[i]<<" ";
51     return 0;
52 
53 }