多重背包¶
问题描述¶
有 \(n\) 种 物品（ 每种物品有 \(N_i\) 个 ） 和 一个容量为 \(W\) 的背包，每个物品有重量 \(w_i\) 和价值 \(v_i\) 两种属性，要求：选若干物品放入背包，使背包中物品的 总价值最大 且 背包中物品的总重量不超过背包的容量
朴素做法¶
与 完全背包问题 类似，考虑对每件物品，枚举其选择件数，得到 状态转移方程：
f[i][j]=max(f[i-1][j-k*w[i]])+k*v[i] ，其中 0<=k<=N[i]
另一种思路是 将其转化为 0-1 背包 问题：
只要把 “种” 换成 “个” 就好了，也就是把 每种物品有 \(N_i\) 个 拆成 \(N_i\) 个相同的物品 ，再用 0-1 背包的方法就可以求解了
可以发现，两种思路的时间复杂度都是 \(\displaystyle O\Big(W×\sum_{i=1}^nN_i\Big)\)
优化¶
可以看到，上面两种思路实际上都是在考虑第 i 种物品时，将 f[i] 拆成 \(N_i\) 个子状态，每个子状态对应一件 i 物品
，再对每个子状态应用决策（取-不取）
如果选两件 i 物品要怎样做呢？很明显，在拆出来的 \(N_i\) 个子状态任选两个应用决策 “取”，其他的都应用决策 “不取” 即可。可以发现，任选两个 将导致大量重复操作
怎么优化呢？
倍增拆分¶
我们可以在拆分时不把 f[i] 完全拆散 ，而是采用 倍增 的思想，将其拆成大小为 1,2,4,8,... 的小块
我们知道，任意正整数都能表示为 2 的不同幂次之和 ，所以这样拆分后，不管选几个都可以通过选 “小块” 实现了
如果 N[i] 不是 2 的连续幂次之和 怎么办呢？把多出来的作为一个块就好了，块大小为
\[N-2^{\lfloor\log_2{(N+1)}\rfloor-1}\]
比如：\(18=(1+2+4+8)+3\)