DP学习_0-1背包问题
时间：2010-08-26 来源：长江西岸
问题描述：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。
算法分析：
DP的问题可以转化为一种维护备忘录（表）的思想，0-1背包问题是DP的基本问题，其本质在于自底向上地维护下面所示的一张表：
案例假设：n=3; c=6;
物品的重量w与价值v如下：
|
物品 |
0 |
1 |
2 |
|
w |
3 |
2 |
1 |
|
v |
3 |
2 |
1 |
程序要维护的表（人工算出）：
|
i j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
2 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
2 |
3 |
3 |
3 |
3 |
|
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
维护过程说明：
首先在初始化时提供i=2这一行的值，程序运行时遵循以下原则：
1. 当i=n-1时，若j>=w[i],则m(i,j)=v[i]；若0<=j<w[i]，则m(i,j)=0
2. 当i<n-1时，若j>=w[i],则m(i,j)=max{ m(i+1,j), m(i+1,j-w[i])+v[i] }；若0<=j<w[i]，则m(i,j)=m(i+1,j)
对于这个规则的分析：
【m(i+1,j) 容量为j，不新添加第i个物品时的最大价值】
【m(i+1,j-wi)+v[i] 容量j去掉第i个物品质量时的最大值（表中在之前已经求出）直接加上v[i]，即强制添加第i个物品】
【需要添加i的情况的剪贴法解释：强制添加第i物品比不添加，总价值更高】
根据以上分析产生的代码：
1 //0-1 Knapsack problem
2 #include <iostream>
3 using namespace std;
4
5 #define MAX_KNAPSACK 10
6 #define MAX_CONTAIN 50
7
8 class KPC
9 {
10 private:
11 int v[MAX_KNAPSACK];//Value
12 int w[MAX_KNAPSACK];//Weight
13 int f[MAX_KNAPSACK][MAX_CONTAIN];//Best Value
14 int c;//Contain
15 int n;
16 int max(int a, int b);
17 int min(int a, int b);
18 public:
19 void DP();//物品起始号，当前容量
20 };
21
22 int KPC::max(int a, int b)
23 {
24 return a > b ? a : b;
25 }
26
27 void KPC::DP()
28 {
29 cin >> n >> c;//先输入物品数，然后是容量
30 for(int i=0; i!=n; i++)
31 {
32 cin >> v[i] >> w[i];//先价值，后重量
33 }
34
35 //初始化第一行的值作为基点
36 f[n-1][0] = 0;
37 for(int j=1; j<=c; j++)
38 {
39 f[n-1][j] = 1;
40 }
41
42 for(int j = 0; j <= c; j++)//按上到下、左到右顺序填表
43 {
44 for(int i=n-2; i>=0; i--)//总质量一定，找到最优值
45 {
46 if(j < w[i])
47 {
48 for(int t=j; t<=w[i]; t++)
49 {
50 f[i][t] = f[i+1][j];
51 }
52 }
53 else//j == w[i]
54 {
55 f[i][j] = max(f[i+1][j], f[i+1][j-w[i]] + v[i]);
56 }
57 }
58 }
59
60 //输出右下角的值作为最大价值的解
61 cout << f[0][c] << endl;
62 //打印填好的表
63 for(int i=n-1; i>=0; i--)
64 {
65 for(int j=0; j<=c; j++)
66 {
67 cout << f[i][j] << " ";
68 }
69 cout << endl;
70 }
71 }
72
73 int main()
74 {
75 KPC KP;
76 KP.DP();
77 system("pause");
78 }
程序运行的结果：
3 6
3 3
2 2
1 1
6
0 1 1 1 1 1 1
0 1 2 3 3 3 3
0 1 2 3 4 5 6
Press any key to continue . . .
相关阅读 更多 +
