01背包

有 $N$ 个物品和一个容量为 $V$ 的背包, 物品有两个属性: 价值和体积

\text{第}i\text{个物品的价值为}w_i,\text{体积为}v_i

体积为整数

状态定义为

f(i,j)=\text{只考虑前}i\text{件物品,背包容量为}j\text{时能获取的最大价值}

状态转移方程可以这样考虑:考察状态 $f(i,j)$ , 对于 $i$ 个物品可以选择拿走或者不拿走, 如果不拿走则

f(i,j)=f(i-1,j)

拿走则需要腾出 $v_i$ 的空间,即上一步只有 $j-v_i$ 的空间可以用

f(i,j)=f(i-1,j-v_i)+w_i

由此得到状态转移方程

f(i,j)=\max\{f(i-1,j), f(i-1,j-v_i)+w_i\}

鉴于 $f(i,j)$ 只依赖于 $i-1$ 的状态, 可以使用滚动数组减小空间开销

多重背包

有 $N$ 种物品和一个容量为 $V$ 的背包, 物品有三个属性: 数量,价值和体积

\text{第}i\text{种物品的价值为}w_i,\text{体积为}v_i, \text{数量为}s_i

状态依然定义为

f(i,j)=\text{只考虑前}i\text{件物品,背包容量为}j\text{时能获取的最大价值}

考察状态 $f(i,j)$ 时, 需要遍历拿 $0$ 个,拿 $1$ 个, ... ,拿 $s_i$ 个情况, 那么状态转移方程就是

f(i,j)=\max\{f(i-1,j-k\cdot v_i)+k\cdot w_i\},\quad k=0,1,\cdots,s_i

鉴于 $f(i,j)$ 只依赖于 $i-1$ 的状态, 可以使用滚动数组减小空间开销

也可以将其转化为01背包问题, 即将第 $i$ 种物品变为 $s_i$ 件物品. 不过这样朴素地转化, 时间复杂度是相同的, 这不好. 可以优化的点在于考虑了多种相同的情况

0,0,1,1\text{与}0,1,0,1\text{拿的数目是相同的}

一种聪明的方式是利用二进制拆分物品, 像这样

1,2,4,\cdots 2^n

任一拿物品的方案都可以用这些物品组的拿与不拿状况唯一表示, 这样就去除了重复的情况, 时间复杂度将为了

V\sum \log s_i

有 $N$ 种物品和一个容量为 $V$ 的背包, 物品有两个属性: 价值和体积

\text{第}i\text{种物品的价值为}w_i,\text{体积为}v_i

每种物品的数目无限多

一种朴素的做法是如多重背包一般

f(i,j)=\max\{f(i-1,j-k\cdot v_i)+k\cdot w_i\},\quad k=0,1,\cdots

不过这里的 $k$ 选择并没有上限, 唯一约束是不能超过背包容量. 这样做显然复杂度很大, 可以考虑与多重背包相同的二进制优化方案

1, 2, 4, \cdots, 2^k\quad k=\log V/v_i

这样就能将复杂度大大降低