背包九讲 | Grimner

type

status

date

slug

summary

有件物品和一个容量是的背包。每件物品只能使用一次。

第件物品的体积是，价值是。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

解法： 假设表示只看前个物品，总体积是的情况下，总价值最大是多少,只考虑第件物品，如果不放第i件物品，那么就是将前件物品放入体积为背包中，如果放第件物品，就是将件物品放入容量背包中，此时价值加上，

那么显然递推式就是

注意此时对容量进行遍历时，要从大到小,保证每件物品只选择一次。

明显01背包模板问题，考虑优化，根据上面得到的递推式存储结果的作为二维数组使用时，其维在循环中并没有表现出来，所以可以直接省略掉。

有种物品和一个容量为的背包，每种物品都有无限件可用。第种物品的费用是，价值是。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有多种取量选择。

复杂度过高，考虑

一个很简单有效的优化，是这样的：若两件物品满足c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不用考虑。考虑把完全背包问题转化为01背包问题来解。现在完全背包的特点是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果

那么递推依然可以是 f[v]=max{f[v],f[v-c[i]]+w[i]};

但是选择方式不同了，循环容量时从小到大进行选择，可以选取时就尽量进项选取。

有种物品和一个容量为的背包。第i种物品最多有件可用，每件费用是，价值是。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品可以取0到件

考虑降低复杂度，二进制优化，使每件物品系数分别为，由于计算机01的特性，可以简单地通过位运算进行拆分，将同一种类型的物品分为不同块，近似于01背包的运算。同时复杂度降低为

有件物品和一个容量为的背包。第i件物品的费用是，价值是。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设表示前组物品花费费用能取得的最大权值，则有f[k][i]=max(f[k-1][i-a[j]]+b[j],f[k-1][i]); 即为01背包的变体，提前将分组处理即可。