背包问题是动态规划的常见题目。主要分为01背包、多重背包等。题目一般给出物品个数N、背包体积V。然后输入每个物品的体积V和价值W
一般的解题思路是使用一个二维数组,每一个f[i][j]可以看作一个背包。那么f[i][j]就表示有i个物品放入体积为j的背包最大的价值。对于第i个物品可能出现三种情况：
- 放不下第i个物品 f[i-1][j]
- 可以放下第i个物品，但是不放 f[i-1][j]
- 可以放下第i个物品，放 f[i-1][j-v[i]]+w[i](其中v[i]表示第i个物品的体积，w[i]表示第i个物品的价值
那么
if(j>=volumn[i]){//可以放下
f[i][j]=max(f[i-1][j],f[i-1][j-volumn[i]]+weights[i]);
}
f[i][j]=max(f[i][j],f[i-1][j]);//如果放不下或者可以放下和放不下进行比较
二维数组的空间复杂度为O(n2)，我们可以使用滚动数组的方式来优化空间复杂度。可以看到第i个状态只和i-1的状态有关。那么我们有两种方式进行优化。
1.交替滚动
也就是使用前一个时刻和当前时刻相互进行更新,使用f[2][N]的二维数组。
int pre=1;
int now=0;
for(int i=1;i<=N;i++){
swap(now,pre);
for(int j=1;j<=V;j++{
if(v[i]<=j) f[now][j]=max(f[pre][j],f[pre][j-v[i]]+w[i]);
f[now][j]=max(f[now][j],f[pre][j]);
}
}
此时我们的j从小到大和从大到小都可以。
2.自我滚动
使用一维数组进行自我更新
for(int i=1;i<=n;i++)
for(int j=V;j>=V[i];j--)//这里必须从大到小
{
f[j]=max(f[j],f[j-V[i]]+W[i]);
}
为什么需要从大到小？
如果我们从小到大,那么当我们更新j较大的值的时候。此时一维数组f[i]前面存放的不是i-1的状态而是i的状态。由于是01背包，每个物品只有一个。因此我们不能重复放入一个相同的物品。因此我们需要从大到小进行更新，因为从大到小的时候，假如计算到j在中间大小的时候，我们更新用到的体积较小的i，f[j]=max(f[j],f[j-V[i]]+w[i])此时f[j-V[i]]这个地方存放的是i-1时刻的状态，因为从大到小更新的时候f[小]肯定是在f[大]之后进行更新的，所以保存的是上一个时刻的状态即换成二维数组是f[i-1][j]。
如果我们的物品可以无限次放入，那么就是完全背包问题。此时我们需要从小到大更新，因为一个小物品可能被多次放入，我们更新大物品的时候需要的是此时刻的状态。
滚动数组的缺点：
无法记录状态转移的信息，覆盖了中间的状态。导致无法输出具体的方案。