01背包问题详解+优化思路
题干：背包容量为V，一共有n个物品，每个物品1个，每个物品有其属性：价值w与体积v。
题目要求：求 该背包所能容纳物品的价值的和 的最大值。
思路：
1.设置状态变量
令 dp[i][j] 表示选择 i 个物品，体积不超过 j 的情况下所产生的价值最大值。
2.列出状态转移方程
对于一个物品存在两个状态：被选 与 不被选。
根据此我们可以列出以下状态转移方程：
设已选择 i 个物品，体积不超过 j。
dp[i][j] = max(dp[i][j], (dp[i - 1][j - v[i]] + w[i]));
根据方程可知，dp[i][j]的值由两个值所推出，分别是：
-
当前物品不选，
dp[i][j]的值保持不变，即其本身d[i][j]。 -
当前物品被选，因为
dp[i][j]表示在求 已选择 i 件物品情况下，体积不超过 j 的价值最大值，所以其值一定是从[dp[i - 1][j -v[i]]][1]推导出来的（这里很难理解，请参考注释并反复阅读）。其值为上一个状态加上当前物品的价值，即dp[i - 1][j - v[i]] + w[i]。
[1]:dp[i - 1][j -v[i]] 表示已选择 i-1 件物品，总体积不超过 j -v[i] 的价值最大值。关于为何为j-v[i]，是因为需要保证 选择当前物品之后 的体积小于等于 j ，就需要保证 选择上一件物品时 的体积不大于 j 减去当前物品的体积，数学式表示：last_j + v[i] <= j => last_j <= j - v[i]。故写成dp[i - 1][j - v[i]]
代码实现：
核心代码：
//枚举物品
for(int i = 1; i <= n; i++)
//枚举体积
for(int j = 0; j <= V; j++)
//若可以装下第i件物品才进行状态更新
if(j >= v[i])
dp[i][j] = max(dp[i][j], (dp[i - 1][j - v[i]] + w[i]));
最终答案：max{dp[0~n][V]}
一维优化：
如图所示：
根据状态转移方程dp[i][j] = max(dp[i][j], (dp[i - 1][j - v[i]] + w[i]));可得出下面的性质：
性质：对于每一个dp[i][j]我们可以发现，其值取决于当前格与上一行的j - v[i]格，由于v[i] > 0，所以j - v[i]一定小于 j。图中红色部分可得出dp[i][j]的值。
我们是否可以根据这一性质进行优化呢？可以。
如图：只要知道dp[i - 1][0 ~ (j - 1)]和dp[i][j]可以得出任意一个dp[i][j]，其他部分都不能得出dp[i][j]。
由于是递推，所以可以保证dp[i - 1]行已经是其本身最优解。于是我们可以舍去无用部分，只保留能够推出dp[i][j]的dp[i - 1]与dp[i]两行。
现在数组大小已由n*v大小优化成了2*V大小。
还可以继续优化：我们可以合并dp[i - 1] 和 dp[i]两行，舍去无用数据。此时数组变为一维数组。
如图所示：
这一个数组中包含了两个状态：在求dp[j]（即dp[i][j]）时，dp[0 ~ (j - 1)]为原来的dp[i - 1][0 ~ (j - 1)]，
而dp[j ~ V]为原来的dp[i][j ~ V]。
由此得知，dp[0 ~ j]可以得出任意一个dp[j]的值，前提是dp[0 ~ (i - 1)]表示的数为原来的dp[i - 1][0 ~ (i - 1)]而不是dp[i][0 ~ (i - 1)]。
为了让dp[i - 1][0 ~ (i - 1)]的状态不被更新为dp[i][0 ~ (i - 1)]，故我们需要从大往小递推。
核心代码：
for(int i = 1; i <= n; i++)
for(int j = V; j >= 0; j--)
if(j >= v[i])
dp[j] = max(dp[j], (dp[j - v[i]] + w[i]));
或者这样写：
for(int i = 1; i <= n; i++)
for(int j = V; j >= v[i]; j--)
dp[j] = max(dp[j], (dp[j - v[i]] + w[i]));
最终答案：
由于二维数组被优化为一维数组，其含义也就从原来的 已选择 i-1 件物品，总体积不超过 j -v[i] 的价值最大值 变为了总体积不超过 j -v[i] 的价值最大值
故最终答案为dp[V]
