背包九讲 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]...