1、背包问题

YBTJ1267 【例9.11】01背包问题

NOIPJ2005C 采药

基本模型：一个容量为V的背包，在一定的限制条件下，放进最多（或最少）价值的东西。

根据限制条件的不同，分为三种情况：

• 01背包（ZeroOnePack）：每种物品只有一件，即只能选择放或者不放
• 完全背包（CompletePack）：每种物品有无限件
• 多重背包（MultiplePack）：每种物品最多有n[i]件可用

2、01背包动态规划

基本模型：一个容量为V的背包与N件物品，第i件物品的体积是c[i]，价值为w[i]，求将哪些物品装入背包可使得价值总和最大。

维度为：i件物品、j容量的背包

定义状态：设dp[i][j]表示把i件物品放入容量j的背包可获得的最大价值。

对于第i件物品（体积为c[i]，价值为w[i]）：

• 不放到背包里，则最大价值为dp[i-1][j]
• 放到背包里，则最大价值为dp[i-1][j-c[i]] + w[i]

状态转移方程为：

• 初始化：dp[0][j] = 0, dp[i][0] = 0
• j < c[i]：dp[i][j] = dp[i-1][j]
• j>=c[i]：dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]] + w[i])

3、理解过程

假设背包容量V=8，物品数量N=4：

物品编号	1	2	3	4
体积c	2	3	4	5
价值w	3	4	5	6

3.1 第一步：初始化

• dp[i][0]和dp[0][j]都为0
• 前两列体积c和价值w，为方便查询

c	w	i\j	0	1	2	3	4	5	6	7	8
-		0	0	0
2	3	1
3	4	2
4	5	3
5	6	4

3.2 第二步：怎么填？

• 1的列：由于1 < c[1]（体积为2）所以dp[1][1] = dp[1-1][1] = 0
  • 同样，dp[2][1]、dp[3][1]、dp[4][1]等都是0
• dp[1][2]：由于2==c[1], dp[1][2]=max(dp[1-1][2], dp[1-1][2-2] + 3) = 3
  • 理解：把1物品放进去，体积为2，获得价值为3
• dp[2][2]：由于2<c[2], dp[2][2] = dp[2-1][2] = 3
  • 理解：2物品放不进去，所以还是只能放一个1物品
• ....依次类推到dp[1][3]、dp[1][4]...、dp[1][8] 都为3

c	w	i\j	0	1	2	3	4	5	6	7	8
-		0	0	0
2	3	1		0	3	3
3	4	2
4	5	3
5	6	4

3.3 第三步：dp[2][3]

dp[2][3] = max(dp[2-1][3], dp[2-1][3-c[2]]+w[2])=max(3, 0+4)=4

• 理解：物品1或物品2都可以放进去，选择价值大的：
• 物品2放进去，则剩余容量为0，为dp[1][0] + w[2]=4
• 物品2不放进去，为dp[1][3]=3

c	w	i\j	0	1	2	3	4	5	6	7	8
-		0		0	0
2	3	1	0		3	3	3
3	4	2	0			4
4	5	3
5	6	4

dp[2][3]更直观的理解：

• 如果放进去
  • 本列第一行的3，减去本行的体积列(c[i])，结果为0
  • 找到上一行的0列的值，值为0
  • 0加上本行的价值列(w[i])，结果为4
• 如果不放进去：取上一行的本列的，值为3
• dp[2][3]填写4和3的最大值4

3.4 最后结果，按以上理解逐步填写

c	w	i\j	0	1	2	3	4	5	6	7	8
-		0	0		0
2	3	1			3	3
3	4	2				4	4	7	7
4	5	3					5		8	9	9
5	6	4									10

最后，dp[4][8] = 10

4、关键代码

for(int i=1; i<=N; i++)
for(int j=1; j<=V; j++) {
  if(j >= c[i])
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]] + w[i]);
  else
    dp[i][j] = dp[i-1][j];
}

优化

1、复杂度

以上动态规划的时间复杂度与空间复杂度均为O(N* V)。

但空间复杂度可以优化到O(m)，因为每一次状态转移只与上一行的值有关，我们可以：

• 状态只用一维数组
• 同一行里，从后往前填写，这样前面的值还被保留（上一行的值）

定义状态：设dp[j]表示把i件物品放入容量j的背包可获得的最大价值。

状态转移方程为：

• 初始化：dp[j] = 0
• j>=c[i]：dp[j] = max(dp[j], dp[j-c[i]] + w[i])

2、记录路径

如果想知道最大价值的方案里，背包里都放了哪些物品，该怎么做？

只要用一个二维数组path来存储每次更新放入的物品，然后从后往前遍历输出。

用path逆推出装入的物品：

• i从N、j从V往下倒序
• 如果Path[i][j]为1，表示被装入：
  • 输出物品i和价值，价值用括号
  • j = j - c[i]
• i = i - 1

如果使用二维状态，则无需path也可以倒推出装入的物品。

3、满背包

有时候，题目会要求背包刚好装满，这种情况与不装满的情况比，初始化不一样：

• 把dp[0][j]（j>0）初始化为负无穷大，表示背包没有装满。
• 把dp[0][i]初始化为0，表示装满了
• 当某个状态为不能装满时，值为负无穷，即使加上w[i]也算负无穷
• 判断某个状态，小于0就表示不能装满

在c++中，一般可用0x3f3f3f3f表示无穷大。

#define inf 0x3f3f3f3f;