参考:
01 背包
题目
有 N 件物品和一个容量为 V 的背包. 第 i 件物品的价值是 w[i], 体积是 v[i], 求将哪些物品装入背包可使价值总和最大.
基本思路
特点: 每一种物品只有一件, 我们只能选择放或者不放
所以我们用 dp[i][j]表示前 i 件物品放入容量为 j 的背包能获得的最大价值.
所以得到状态转移方程:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
为什么可以得到这样的状态转移方程呢?
仔细思考 dp 的适用情景(见 dp 从入门到劝退 1)
"将前 i 件物品放入容量为 j 的背包中" 这个子问题, 若只考虑第 i 件物品的策略 (放或不放), 那么就可以转化为一个只牵扯前 i?1 件物品的问题. 如果不放第 i 件物品, 那么问题就转化为 "前 i?1 件物品放入容量为 j 的背包中", 价值为 dp[i?1][j]; 如果放第 i 件物品, 那么问题就转化为 "前 i?1 件物品放入剩下的容量为 j?w[i] 的背包中", 此时能获得的最大价值就是 dp[i?1][j?w[i]]再加上通过放入第 i 件物品获得的价值 v[i].
所以我们将大问题转化为相似的小问题, 而且 01 背包能很好地体现 "无后效性".
题目:
hdu 2602 Bone Collector http://acm.hdu.edu.cn/showproblem.php?pid=2602
问题描述:"骨头收集者" 带着体积 C 的背包去捡骨头, 已知每个骨头的体积和价值, 求能装进背包的最大价值. N <= 1000,C<= 1000.
输入: 第 1 行是测试数量; 后面每 3 行是 1 个测试, 其中第 1 行是骨头数量 N 和背包体积 C, 第 2 行是每个骨头的价值, 第 3 行是每个骨头的体积.
输出:
最大价值.
样例输入:
- 1
- 5 10
- 1 2 3 4 5
- 5 4 3 2 1
样例输出:
14
来源: http://www.bubuko.com/infodetail-3508171.html