背包问题九讲笔记_01背包
背包问题是动态规划中最基本的题目。
动态规划的4步骤：
1.找出子结构
2.递归
3.自底而上
4.求最优解
01背包问题描述
已知:有一个容量为V的背包和N件物品，第i件物品的重量是weight[i]，收益是cost[i]。
限制:每种物品只有一件，可以选择放或者不放
问题:在不超过背包容量的情况下，最多能获得多少价值或收益
相似问题:在恰好装满背包的情况下，最多能获得多少价值或收益
这里，我们先讨论在不超过背包容量的情况下，最多能获得多少价值或收益。
基本思路
01背包的特点:每种物品只有一件，可以选择放或者不放
子问题分析：
f[i][v] : 前i件物品放到一个容量为v的背包中可以获得最大价值
状态转移方程：
f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] + cost[i])
分析
考虑我们的子问题，将前i件物品放到容量为v的背包中，若我们只考虑第i件物品时，它有两种选择，放或者不放。
- 如果第i件物品不放入背包中，那么问题就转换为：将前i - 1件物品放到容量为v的背包中，带来的收益f[i - 1][v]
- 如果第i件物品能放入背包中，那么问题就转换为：将前i - 1件物品放到容量为v - weight[i]的背包中，带来的收益f[i - 1][v - weight[i]] + cost[i]
核心代码：
for(i = 1; i < n ; i ++)
for( j = 1; j < V ; j ++)
{
pd[i][j] = pd[i-1][j];
if( weight[i] <= j )
pd[i][j] = max(pd[i - 1][j],pd[i - 1][j - weight[i]] + cost[i]) ;
}
效率分析：
此算法的时间复杂度为O(NV)，空间复杂度也为O(NV)。其中，N 表示物品个数，V 表示背包容量这里，时间复杂度不可以在优化了，但是空间复杂度可以继续优化到O(V)
优化空间复杂度
上述的方法，我们使用二维数组 f[i][v] 保存中间状态，这里我们可以使用一维数组f[v]保存中间状态就能得到结果
分析
我们现在使用f[v]保存中间状态，我们想要达到的效果是，第i次循环后，f[v]中存储的是前i个物体放到容量v时的最大价值,即对应二维数组的f[i][v]
根据上面的状态转移方程，
f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] + cost[i])
可以知道,要想得到f[v]，前i - 1个物品放到容量v的背包中带来的收益，即之前的f[i - 1][v] 和 前i - 1件物品放到容量为v - weight[i]的背包中带来的收益，即之前的f[i - 1][v - weight[i]] + cost[i]。
在一维数组f[v]中，在执行在i次循环时，f[v]存储的是前i个物体放到容量v时的最大价值。即此时的f[v]相当于之前的f[i-1][v]正是我们需要知道的第一项。
而f[v-weight[i]]+cost[i]就是需要求的第二项。
求f[v]还好，此时的f[v]就是f[i-1][v]。但是如果依旧是增序遍历容量，那么当处理f[v]的时候 f[v-weight[i]]已经被处理过，此时f[v-weight[i]]的意义就变成前i个物品放到容量v-weight[i]背包中的收益了，那么就直接失去了f[i - 1][v - weight[i]]。
因此需要 逆序遍历容量 （V....0）才能做到 在第i次循环中，处理f[v]的时候，
f[v-weight[i]]还是f[i-1][v-weight[i]]的意义
伪代码：
for i=1..N //枚举物品
for v=V..0 //枚举容量，从大到小
f[v]=max{f[v],f[v-weight[i]] + cost[i]};
