DP查缺补漏之01背包优化原理

状态假设
- DP[I][J]为前$i$个物品，容量小于$j$时的最优解（最大价值）
状态转移
- DP[I][J] = max(DP[I - 1][J], DP[I - 1][J - V[I]] + W[I])
  - 对于第$i$个物品，两种可能
    - 装入背包
      - 则状态应通过前$i - 1$个物品，容量小于$j$时的最优解再加上W[I]转移，但是实际上本次状态的容量才为$j$，若直接从DP[I-1][J]转移则忽略了该物品体积，所以应从减去该次物品体积的DP[I - 1][J - V[I]]转移。即DP[I - 1][J - V[I]] + W[I]
      - 证明此解严谨性
        
        上一层循环已然计算了DP[I - 1][0 ~ M]的所有最优解
        
        则DP[I - 1][J - V[I]]已经是最优解
    - 不装入背包
      - 则状态应通过前$i - 1$个物品，容量小于$j$时的最优解直接进行转移
代码处理
- 开二维数组来对标状态假设
- 初始化DP[0][0~M]为$0$
- 两层循环递推，外层枚举$1 \sim i$，内层枚举$ 1 \sim m $
- 进行DP[I][J] = DP[I - 1][J - V[I]] + W[I]状态转移时必须确保$J > V[I]$

从状态转移方程入手
- DP[I][J] = max(DP[I - 1][J], DP[I - 1][J - V[I]] + W[I])
  - 每个DP[I][J]都是从DP[i-1][x]转移而来
  - 显然可以用滚动数组
具体化优化思路
- 直接删除第一维
  - 用循环来直接进行对上一维的转移
  - ```
  for(int i=1;i<=n;i++)
  {
  	for(int j=W[i];j<=M;j++)
  	{
  		dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
  	}
  }
```
- 但这有一个问题，此时的dp[j - w[i]]实际上就是本次$i$的，因为是从小到大递推的，要操作每一个dp[i - 1][j]的时候都已经被更新成此次状态的dp[i][j]了，此时需要一个妙手，第二层循环反着枚举
- ```
for(int i=1;i<=n;i++)
{
	for(int j=M;j>=w[i];j--)
	{
		dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	}
}
```
  - 因为所有大的都是由小的转移而来，由大至小的枚举使得每一次要取dp[j-w[i]]时，dp[j-w[i]]都是$i$上一次循环的最优解，不会被更新。