代码思想都是参考y总的
各位神犇别嘲笑我这个蒟蒻

01背包&&完全背包优化问题(有图有真相)

01背包优化讲解

明白了$f[i][j]$ 的含义之后，我们可以将01背包的状态转移方程写成：

$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])$

那么我们可以画一个矩阵来分析

蓝色: $f[i][j]$

黄色: $f[i-1][j]$

绿色: $f[i-1][j-v[i]]$

$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])$

我们可以由👆的状态转移方程和👆的图1得到 $f[i][j]$ 只需要上一行的数据，而且是左上($蓝色 = 黄色+绿色$)

那么我们可以把二维的矩阵优化成为一维的数组，所以我们只需要用到 $j$

此时我们将方程写出来: $f[j]=max(f[j],f[j-v[i]]+w[i])$ 。

我们可以观察未进行空间优化的代码

我们的 $f[i][j]$ 只需要左上的数据，如果我们让$j$ 递增的遍历，那么我们除了用到了

$f[i-1][j]$ 而且还用到了同一层 $f[i][j-v[i]]$

然而状态方程 :$f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])$ 我们需要的是上一层的数据。

所以如果我们让 $j$ 递减的遍历，那么我们用到的就是上一层 $i-1$ 的 $j$ 往左的数据了。

for(int i=1;i<=n;i++) 
{
    for(int j=v[i];j>=m;j++)
    {

        /* 未进行空间优化的代码
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i])
            f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);  
        }
        */

        f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
}

return f[m];

完全背包优化讲解

知道了01背包的优化方法之后，我们可以类比来看完全背包

状态转移方程 $f[i][j]=max(f[i-1][j],f[i][j-v[i]+w[i])$

其实除了直接用数学归纳法从三个for循环优化到两个for循环

还是可以直接从状态表示来理解。$f[i][j-v[i]]+w[i]$

我们在取了许多物品之后，在体积不超过 $j$ 的情况下再添加一件 $i$ 物品和 $f[i-1][j]$

进行比较，取一个 $max$

让我们再看一下👇的图2:

蓝色: $f[i][j]$

黄色: $f[i-1][j]$

红色: $f[i][j-v[i]]$

优化一层空间 $f[j]=max(f[j],f[j-v[i]]+w[i])$

而且我们从01背包问题中可以类比得，在完全背包问题中我们需要的是同一层的数据，

所以我们需要让 $j$ 从小到大递增遍历，这个时候我们用到的就是同一层 $i$ 的数据了。

for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)


/* 1.可以优化一层for循环
for(int k=0;k*v[i]<=j;k++)
f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k;
*/

/* 2.可以优化一层空间
f[i][j]=max(f[i][j],f[i][j-v[i]+w[i]);
*/

f[j]=max(f[j],f[j-v[i]]+w[i]);

cout<<f[m];

蒟蒻语文不大好，算法也不大彳亍，尽量写了，希望能看得懂吧。。。

acwing的分享排版有点难搞，和我的typora不大一样，尽力了。。。