【Day1】 背包简单复习

01背包

最简单的一种背包,状态转移方程是

分别对应第 $i$ 件物品的拿于不拿

空间压缩有 01滚动就地滚动
01滚动 就是 $F[2][v]$ 这样的。

01背包在就地滚动的时候,忧郁要用上一层的信息,所以要从后往前滚动。

1
2
3
def ZeroOnePack(F,C,W):
for v = V to C:
F[v] = max(F[v],F[v-C] + W)

完全背包

每种物品有无限个。
状态转移方程

第二项改成了 $F[i]$ ,若通过第二项转移,则相当于又拿了一个 第 $i$ 件物品

就地滚动的时候要从前往后滚

1
2
3
def CompletePack(F,C,W):
for v = C to V:
F[v] = max(F[v],F[v-C] + W)

多重背包

每种物品有多个

第 $i$ 件物品最多有 $M_i$ 件可用

思路: 二进制拆分

1
2
3
4
5
6
7
8
9
10
def MultiplePack(F,C,W,M):
if C*M >= V: #足够多,可以看作完全背包
CompletePack(F,C,W)
return
k := 1
while k < M:
ZeroOnePack(F,kC,kW)
M := M - k
k *= 2
ZeroOnePack(F,MC,MW)

二维费用的背包问题

每件物品有两种耗费

这是对应01背包的转移方程,完全背包同理

当每件物品只能取一次的时候,变量$v$ 和变量$u$采用逆序的循环

当物品无限的时候,变量$v$ 和变量$u$采用顺序的循环