0-1背包与完全背包的不同
本文转自CSDN，原文：https://blog.csdn.net/qiaoruozhuo/article/details/76167137
分析：
0-1背包和完全背包问题的区别在于前者同一种物品最多选一次，而后者同一种物品可多次选取。我们使用B[i][j]表示从前i件物品中选出若干件物品放在容量为j的背包中，所得的最大价值，可以得到二者的状态方程分别为：
0-1背包问题：B[i][j] = B[i-1][j]，其中j < W[i]；
或者B[i][j] = max(B[i-1][j], B[i-1][j-W[i]] + P[i])，其中j >= W[i]。
完全背包问题：B[i][j] = B[i-1][j]，其中j < W[i]；
或者B[i][j] = max(B[i-1][j], B[i][j-W[i]] + P[i])，其中j >= W[i]。
二者状态方程的区别在于：
0-1背包问题中，若取了1件第i个物品，则总容量变为j-W[i]，剩下的只能在前i-1件物品中去取了，其最大总价值为B[i-1][j-W[i]] + P[i]；
完全背包问题中，若取了1件第i个物品，则总容量变为j-W[i]，剩下的仍可以在前i件物品中去取，其最大总价值为B[i][j-W[i]] + P[i]；
一维数组优化算法:
0-1背包问题：
B[i][j] = max(B[i-1][j], B[i-1][j-W[i]] + P[i])，即第i行第j列的元素，由第i-1行的元素决定，且列坐标j大的元素由j小的元素决定，若我们用一维数组F[j]代替B[i][j]，则只记录了列坐标，未记录行坐标，在同一行中，必须先求出列坐标较大的元素，再求列坐标小的元素，这样先改变的是下标j较大的元素，且其不会影响j小的元素。故在内层循环中，应该让循环变量j的值从大到小递减。
完全背包问题：
B[i][j] = max(B[i-1][j], B[i][j-W[i]] + P[i])，即第i行第j列的元素，可能是等于第i-1行第j列的元素，也可能由第i行第j-W[i]列的元素决定，故必须先求出同一行中列坐标j较小的元素，用来计算j较大的元素。 若我们用一维数组F[j]代替B[i][j]，则只记录了列坐标，未记录行坐标，在同一行中，必须先求出列坐标j较小的元素，再求j大的元素，故在内层循环中，应该让循环变量j的值从小到大递增（与0-1背包问题刚好相反）。
总结：
二者的状态方程很相似，区别在于B[i][j]是由上一行的较小列坐标决定，还是由同一行的较小列坐标决定，使用二维数组记录最优解时，我们可以直接根据状态方程求B[i][j]，因为同时记录了元素的行坐标和列坐标值，故无论内层循环的循环变量j是递增还是递减，都不影响计算结果。但是，若使用一维数组F[j]代替B[i][j]，则只记录了列坐标，未记录行坐标，需要考虑先改变列坐标j较大的元素还是j较小的元素。在0-1背包问题中，须先求出列坐标j较大的元素，故让循环变量j的值从大到小递减；而完全背包问题中，须先求出列坐标j较小的元素，故让循环变量j的值从小到大递增。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
using namespace std;
const int MAXC = 12880; //背包最大容量
const int MAXN = 3402; //物品的个数
int W[MAXN+1];//物品的重量
int P[MAXN+1];//物品的价值
int F1[MAXC+1]; //记录装入容量为c的背包的最大价值
int B1[MAXN+1][MAXC+1]; //备忘录，记录给定n个物品装入容量为c的背包的最大价值
int F2[MAXC+1]; //记录装入容量为c的背包的最大价值
int B2[MAXN+1][MAXC+1]; //备忘录，记录给定n个物品装入容量为c的背包的最大价值
int Best_1(int n, int c); //0-1背包问题：二维数组记录最优解
int Best_2(int n, int c);//0-1背包问题：一维数组记录最优解
int Best_3(int n, int c);//完全背包问题：二维数组记录最优解
int Best_4(int n, int c);//完全背包问题：一维数组记录最优解
int main()
{
int n, c;
cin >> n >> c;
for (int i=1; i<=n; i++)//不计下标为0的元素
{
cin >> W[i] >> P[i];
}
cout << Best_1(n, c) << endl;
cout << Best_2(n, c) << endl;
cout << Best_3(n, c) << endl;
cout << Best_4(n, c) << endl;
return 0;
}
int Best_1(int n, int c)//0-1背包问题：二维数组记录最优解
{
//记录前i(1<=i<n)个物品装入容量为0-c的背包的最大价值
for (int i=1; i<n; i++)
{
for (int j=0; j<W[i]; j++)//背包容量不够，不能装下第i件物品
{
B1[i][j] = B1[i-1][j];
}
for (int j=W[i]; j<=c; j++)//背包容量足够，可以选择装或不装第i件物品
{
if (B1[i-1][j] < B1[i-1][j-W[i]] + P[i])
B1[i][j] = B1[i-1][j-W[i]] + P[i];
}
}
//因为第n个物品最多装一次，故只要容量够，未装满与装满的价值是一样的，即B1[n][c]==B1[n][j]，其中W[n]<=j<=c
//所以对第n个物品来说，只需考虑容量恰好为c的情况，这样可以减少计算量
if (c < W[n]) //如果容量不够
{
B1[n][c] = B1[n-1][c]; //先默认为不装第n个物品
}
else
{
B1[n][c] = max(B1[n-1][c], B1[n-1][c-W[n]]+P[n]);
}
return B1[n][c];
}
int Best_2(int n, int c)//0-1背包问题：一维数组记录最优解
{
//为简化代码，没有把i==n的情形单独拿出来处理，若需要单独处理第n个物品，可参考Best_1()
for (int i=1; i<=n; i++)
{//须先求出列坐标j较大的元素，故让循环变量j的值从大到小递减
for (int j=c; j>=W[i]; j--)
{//当(j < W[i] || F1[j] > F1[j-W[i]] + P[i])时，F1[j]的值不变
if (F1[j] < F1[j-W[i]] + P[i])
F1[j] = F1[j-W[i]] + P[i];
}
}
return F1[c];
}
int Best_3(int n, int c)//完全背包问题：二维数组记录最优解
{
for (int i=1; i<=n; i++)
{
for (int j=1; j<W[i]; j++)//容量不够，则和给定i-1个物品装入容量为j的背包的结果一致
{
B2[i][j] = B2[i-1][j];
}
for (int j=W[i]; j<=c; j++)
{//B2[i][j-W[i]]表示给定i个物品装入容量为j-W[i]的背包，质量为W[i]的物品可能装了多个
B2[i][j] = max(B2[i-1][j], B2[i][j-W[i]] + P[i]);
}
}
return B2[n][c];
}
int Best_4(int n, int c)//完全背包问题：一维数组记录最优解
{
for (int i=1; i<=n; i++)
{//须先求出列坐标j较小的元素，故让循环变量j的值从小到大递增
for (int j=W[i]; j<=c; j++)
{//当(j < W[i] || F2[j] > F2[j-W[i]] + P[i])时，F2[j]的值不变
if (F2[j] < F2[j-W[i]] + P[i])
F2[j] = F2[j-W[i]] + P[i];
}
}
return F2[c];
}
|
