Algorithm | 背包问题

背包问题九讲学习

0-1背包问题

• $N$个物品
• 一个容量为$V$的背包
• 每种物品仅有一个，可以选择“放入背包”或“不放入背包”
• 放入第$i$个物品耗费的费用为$C_i$（占用背包的空间容量），得到的价值为$W_i$

$$将哪些物品装入背包可使获得的价值总和最大$$

在线编程：https://www.acwing.com/problem/content/2/

思路

考虑$N$行$V$列的矩阵，第$i$行第$v$列的元素为$F(i,v)$表示前$i$个物品恰好放入一个容量为$v$的背包所能获得的最大价值

• 若不放第$i$个物品，则问题为“前$i-1$个物品放入容量为$v$的背包”，则能获得的最大价值为“前$i-1$个物品放入容量为$v$的背包”可获得的最大价值。即
  $$F(i,v)=F(i-1,v)$$
• 若放入第$i$个物品，则问题为“前$i-1$个物品放入容量为$v-C_i$的背包”，则能获得的最大价值为“前$i-1$个物品放入容量为$v-C_i$的背包”可获得的最大价值加上“放入第$i$个物品”可获得的价值。即
  $$F(i,v)=F(i-1,v-C_i)+W_i$$
  因此
  $$F(i,v)=\max \left{ F(i-1,v), F(i-1,v-C_i)+W_i \right}$$

伪代码

1. 给定$N$行$V$列的空矩阵$F$，用于存储$F(i,v)$
2. 对于$i=1,2,\cdots,N$， $v=C_i,\cdots,V$有
   $$F(i,v)=\max\left{F(i-1,v), F(i-1,v-C_i)+W_i\right}$$

• 时间复杂度为$O(NV)$
• 空间复杂度为$O(NV)$

## 在线编程地址：https://www.acwing.com/problem/content/2/
## 二维数组实现
N, V = list(map(int, input().split()))
goods = []
for i in range(N):
    goods.append(list(map(int, input().split())))  ## 存放物品的体积、价值等信息

F = [[0 for j in range(V+1)] for i in range(N+1)]

for i in range(1, N+1):
    for v in range(1, V+1):
        F[i][v] = F[i-1][v]  ## 不装入第i个物品
        if v >= goods[i-1][0]:  ## 如果背包容量大于第i个物品的体积
            F[i][v] = max(F[i][v], F[i-1][v - goods[i-1][0]] + goods[i-1][1])  ## 选取价值最大的方案

print(F[-1][-1])  ## 最后一个值为最大价值

思路优化

考虑优化空间复杂度

上面的思路中，用$N$行$V$列的矩阵来存储信息，需要$NV$个存储位置，考虑将存储空间优化成$O(V)$
$$只用长度为V的列表来存储信息$$

伪代码

1. 给定长度为$V$的列表$F$

2. 对于 $i=1,2,\cdots,N$:
   • 对于 $v=V, V-1, \cdots, C_i$:
     $$F[v]=\max\left{F[v], F[v-C_i]+W_i \right}$$

## 在线编程地址：https://www.acwing.com/problem/content/2/
## 一维数组实现
N, V = list(map(int, input().split()))
goods = []
for i in range(N):
    goods.append(list(map(int, input().split())))  ## 存放物品的体积、价值等信息

F = [0 for j in range(V+1)]

for i in range(N):
    for v in range(V, -1, -1):
        if v >= goods[i][0]:
            F[v] = max(F[v], F[v - goods[i][0]] + goods[i][1])

print(F[-1])

实例

有个背包，可以装4磅的东西。怎样装以下的商品，可以使得背包里的东西价值最高？

• 音响：3000美元，4磅
• 笔记本电脑：2000美元，3磅
• 吉他：1500美元，1磅

	1	2	3	4
吉他	$1500	$1500	$1500	$1500
音响	$1500	$1500	$1500	$3000
笔记本电脑	$1500	$1500	$2000	$3500

• 只考虑第1个物品——吉他，1~4容量的背包最多可容纳1500美元的物品（只能装吉他）
  $$F(1,1)=F(1,2)=F(1,3)=F(1,4)=1500$$

• 考虑前2个物品——吉他和音响
• 容量为1、2、3的背包都只能装吉他（1磅），获得的价值为1500美元
  $$F(2,1)=F(2,2)=F(2,3)=1500$$
• 若容量为4的背包装音响（4磅），就只能装音响了，获得的价值为3000美元
• 若容量为4的背包不装音响，可装吉他，获得的价值为1500美元
• 3000>1500，因此选择装音响
  $$F(2,4)=3000$$
• 考虑前3个物品——吉他、音响、笔记本电脑
• 容量为1、2的背包都只能装吉他（1磅），获得的价值为1500美元
  $$F(3,1)=F(3,2)=1500$$
• 若容量为3的背包装笔记本电脑（3磅），则只能装笔记本电脑，获得的价值为2000美元
• 若容量为3的背包不装笔记本电脑，则只能装吉他（1磅），获得的价值为1500美元
  $$F(3,3)=2000$$
• 若容量为4的背包装笔记本电脑，则可装笔记本电脑和吉他（共4磅），获得的价值为2000+$F(2,1)$=3500
• 若容量为4的背包不装笔记本电脑，则可获得的最大价值为$F(2,4)$=3000
  $$F(3,4)=3500$$

完全背包问题

多重背包问题

混合背包问题

二维费用的背包问题

分组背包问题

背包问题求方案数

最优方案

有依赖的背包问题

参考资料

• 背包问题九讲