Created
February 14, 2018 19:22
-
-
Save jianminchen/7d754b22d276c6575388150d1bfd4dd9 to your computer and use it in GitHub Desktop.
背包问题
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
背包九讲:http://www.cnblogs.com/jbelial/articles/2116074.html | |
P01: 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]=max{f[v],f[v-c[i]]+w[i]}; | |
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}, | |
因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了 | |
f[i][v]由f[i][v-c[i]]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维 | |
数组解01背包问题是十分必要的。 | |
总结 | |
01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往 | |
也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化 | |
的空间复杂度。 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment