背包九讲_背包九讲VIP专享

背包九讲 P 01: 01背包问题 题目 有N 件物品和一个容量为V 的背包。第i 件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[i][v]表示前i 件物品恰放入一个容量为v 的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i 件物品放入容量为v 的背包中”这个子问题，若只考虑第i 件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1 件物品的问题。如果不放第i 件物品，那么问题就转化为“前i-1 件物品放入容量为v 的背包中”；如果放第i 件物品，那么问题就转化为“前i-1 件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i 件物品获得的价值w[i]。 注意 f[i][v]有意义当且仅当存在一个前i 件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[i][v-1]，这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以，由你自己来体会了。 优 化空 间 复 杂 度 以上方法 的时间 和空 间 复 杂 度 均 为O(N*V)，其中时间 复 杂 度 基本已 经 不能再优 化了，但 空间 复 杂 度 却 可以优 化到 O(V)。 先 考虑上面 讲的基本思路如何 实 现 ，肯 定是有一个主 循 环 i=1..N，每次 算 出来二 维 数 组f[i][0..V]的所有值。那么，如果只用一个数 组 f [0..V]，能不能保证第i 次 循 环 结 束 后f[v]中表示的就是我 们 定义的状态f[i][v]呢 ？ f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两 个子问题递推而来，能否 保证在推f[i][v]时（也 即在第i 次 主 循 环 中推f[v]时）能够 得到 f[i-1][v]和f[i-1][v -c[i]]的值呢 ？ 事 实 上，这要求在每次 主 循 环 中我 们 以v=V..0 的顺 序 推f[v]，这样才 能保证推f[v]时 f[v-c[i]]保存的是状态f[i -1][v-c[i]]的值。伪 代 码 如下： for i=1..N for v=V..0 f[v]...