01背包问题
目录
1——问题概览
2——DP实现(状态转移方程推论)
3——对于01背包问题的优化 二维到一维
问题概览
难度：普及 题目：YBT1267 01背包问题(模版)
描述：
一个旅行者有一个最多能装MMM公斤的背包，现在有nnn件物品
它们的重量分别是W1，W2，...,WnW_1，W_2，...,W_nW1 ，W2 ，...,Wn ,它们的价值分别为C1,C2,...,CnC_1,C_2,...,C_nC1 ,C2 ,...,Cn
求旅行者能获得最大总价值。
DP实现(状态转移方程推论)
首先为什么要叫这为01背包问题？？？
由题可得，对于任一物品只有拿取或者不拿这两种选择(对于一次选择，执行或不执行)
因此也就由"01"代表这个意思了，这是背包问题的root也是最简单的背包问题
如果用普通的搜索来解决，时间复杂度是O(2n)O(2^n)O(2n)，这简直惊为天人！！！
思考下，我们可以把问题分阶段为取第iii件物品且容量为vvv时可获得的最大价值，从第111件商品与背包容量为111时开始往后递推，找到每一阶段的最大值，最终肯定能找到全局最优解，满足动态规划的最优子结构特点
因为前面i−1i-1i−1物品已经为最优了，所以只需要看放第iii个物品和不放第i个物品所获的价值哪个大
但放下也有前提条件，就是第iii个物品重量要小于当前背包容量vvv，不然你就算把背包掏空也塞不下......
简易分析得以下结论
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
A.放不了：直接不放这个物品，最优解——放这个物品前的最优解
B.放得下：
a.先清空背包，只放这个物品，再看看剩余容量能否装下之前的物品，最优解——这个物品的价值+背包剩余容量的最优解
b.不放这个物品，最优解——放这个物品前的最优解
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
然后，a、b 情况进行比较，选出真正的最优解
设DP[i][v]DP[i][v]DP[i][v]为当操作物品为iii个,背包容量为vvv时所获最大价值
状态转移方程就是DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value)DP[i][v]=max(DP[i-1][v],DP[i-1][v-i.weight]+i.value)DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value)
注：i.weighti.weighti.weight指第iii件物品的重量 valuevaluevalue指第iii件物品的价值
代码实现如下
对于01背包问题的优化 二维到一维
其实对于01背包的时间已经到O(M∗N)O(M*N)O(M∗N)了，没法再优化了
但对于空间却可以进一步压缩
我们重新定义DP[v]DP[v]DP[v]为背包容量为vvv下所获的最大价值
根据我们上文的分析DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value)DP[i][v]=max(DP[i-1][v],DP[i-1][v-i.weight]+i.value)DP[i][v]=max(DP[i−1][v],DP[i−1][v−i.weight]+i.value)
其中DP[i−1][v]DP[i-1][v]DP[i−1][v]和DP[i−1][v−i.weight]DP[i-1][v-i.weight]DP[i−1][v−i.weight]都是上一次操作时，容量为vvv和v−i.weightv-i.weightv−i.weight下所得最大价值
可知每一次的DP[i][v]DP[i][v]DP[i][v]都依赖上一轮的最大值
但是我们可以使用逆推来省去[i−1][i-1][i−1]的步骤，因为在一轮iii之后的i+1i+1i+1轮中DP[v]DP[v]DP[v]存储的都是上一次所能获得的最大值
这就使得DP[v−i.weight]DP[v-i.weight]DP[v−i.weight]代替了DP[i−1][v−i.weight]DP[i-1][v-i.weight]DP[i−1][v−i.weight]的功能，并且压缩了空间
状态转移方程为：DP[v]=max(DP[v],DP[v−i.weight]+i.value)DP[v]=max(DP[v],DP[v-i.weight]+i.value)DP[v]=max(DP[v],DP[v−i.weight]+i.value)
注：DP[v]DP[v]DP[v]为不放时所获的值 DP[v−i.weight]+i.valueDP[v-i.weight]+i.valueDP[v−i.weight]+i.value为放时所获的值
If you have QuestionIf\ you\ have\ QuestionIf you have Question为什么使用逆推不用顺推？？？ 初学的本蒟蒻在一开始整理个人笔记时也有该问题...
但是如果你通过YBT原题给出样例去填表发现
很明显顺推情况下DP表是错误的
因为在顺推情况下DP[v]DP[v]DP[v]会存到同一轮前面的值也就是相当于存了DP[i][v−i.weight]DP[i][v-i.weight]DP[i][v−i.weight]但我们要的是DP[i−1][v−i.weight]DP[i-1][v-i.weight]DP[i−1][v−i.weight]
这样在优化后01背包的空间复杂度为O(M)O(M)O(M)了 优化代码：
