九章算法面试题59 背包问题II
浏览数：34 /
时间：2015年06月08日
九章算法官网-原文网址
http://www.jiuzhang.com/problem/59/
题目
有一个大小为m(整数)的背包，和n个体积(大小分别为A[i](整数))和价值（价格分别为B[i](整数))的物品。将这n个物品选一些装到背包中，请问能装价值最大为多少的物品？
在线测试本题
http://www.lintcode.com/en/problem/backpack-ii/
解答
设F[i][j]为前i个物品，选一些组成j的体积，能够获得最大的价值是多少。状态转移方程：f[i][j] = max(f[i-1][j], f[i-1][j-A[i]] + B[i])答案为F[n][0..m] 中取一个最大值。
面试官角度
背包问题是比较常见的面试问题之一。一般来说常见的背包问题的解法需要熟知和熟练。
以下是几道背包问题的在线练习：
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
