dp从入门到劝退2——3大基础背包加优化

参考：https://blog.csdn.net/yandaoqiusheng/article/details/84782655
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

dp从入门到劝退2——3大基础背包加优化

原文：https://www.cnblogs.com/yzdcb/p/12706501.html