动态规划 - 背包篇

reference

https://www.luogu.com.cn/blog/RPdreamer/bei-bao-wen-ti
https://blog.csdn.net/m0_37809890/article/details/79838077

引入（01背包)

for(int i=1;i<=n;i++)
        for(int j=1;j<=V;j++)
            if(j>=c[i]) f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
            else f[i][j]=f[i-1][j];

解释：外层循环是对每一个物品的挑选情况做出判定，内层循环是循环背包的大小。
看到这里有人可能要问了，为什么要循环背包大小呢？因为对于背包来说，挑选的顺序其实无关紧要，也就是说，对于任一一种挑选的顺序，在处理第 i 个物品时，我们不清楚前 i-1 个物品的挑选顺序，也就无从确定第 i 个物品放入后背包的大小。当然有些背包的大小不一定是最佳的，但这无关紧要，因为 max 让我们可以选出最优的方案。

01 背包(一维)

我们注意到，内层循环其实一直在对上一次继承的值进行运算，而且运算顺序和上一一次一样，这也就意味这如果我们把数组换成一维，也不会发生覆盖的情况，于是我们就有一维的01背包

for(int i=1;i<=n;i++)
        for(int j=1;j<=V;j++)
            if(j>=c[i]) f[j]=max(f[j],f[j-c[i]]+w[i]);

但是这样提交的话，你就会欣喜地(并不是)发现你WA了
这又是为什么呢?
假设 i=2,j=1,c[i]=1,f[j-c[i]]+w[i]>f[j]，这时我们选走了 i=2 的物品
当 i=2,j=2 时,我们显然可以发现 f[j-c[i]]+w[i]>f[j]，于是我们又选走了 i=2 的物品
可是物品只有一件啊？问题就出在这里
于是我们要换种方法做

for(int i=1;i<=n;i++)
        for(int j=V;j>=c[i];j--)
            f[j]=max(f[j],f[j-c[i]]+w[i]);

在这种情况下，由于运算时f[j-c[i]]仍未被初始化，所以我们访问的是上一个物品的运算结果，这样就不会出现多次选同一个商品了

满包

改下初始化条件就行了qaq

memset(f,0xC0,sizeof(f)),f[0]=0; // 0xC0是一个比较小的负数值，类似于0x3F

至于为什么这样呢？可以这样理解，就是基本的背包在循环体积的时候，做出选择时 j-c[i] 可能是未被选择过的，也就是说选择的是一个价值为0，但具有体积的背包，但在满包中这样的方案是不可接受的，于是我们把除0之外(体积为0价值自然为0啦)的设置成负无穷，这样就选不上了

常数优化

将二层循环改为 for(int j=V;j>=th;j--) th=max(c[i],V-\sum_{i=1}^nc_i )

我也说不上来是为什么啊qwq(而且只能用于01背包)
原理摘抄自 reference:

下面考虑原文中的优化,这个数值是仅与i有关的.
看了网上大佬的思路,意思是某些算出来的背包实际上对最终结果是没有帮助的.
最多有帮助的就是总体积减去之后每个物品的体积之和.
比如计算最后一件物品时,V-C(n-1)以下容量的背包是不可能转移到结果的.
同理,计算倒数第二件物品时,V-C(n-1)-C(n-2)以下的背包也是不可能转移到最终结果的.

完全背包

应该不用再讲一遍了吧qaq

for(int i=1;i<=n;i++)
        for(int j=c[i];j<=V;j++)
            f[j]=max(f[j],f[j-c[i]]+w[i]);

多重背包

由于完全背包的特性，我们在进行运算的时候确定不了到底取了几次，于是我们只能转化成01背包，把num[i]个的某物品转化为0,1,2,...,num[i]个物品捆绑形成的大物体

(代码来自顾z，懒得写了，直接copy了)

for(int i=1;i<=n;i++)//枚举物品
    for(int j=V;j>=0;j--)//枚举体积
        for(int k=1;k<=num[i];k++)
            //这个枚举到num[i]更省心的 qwq
            if(j-k*c[i]>=0)//判断能否装下.
                f[j]=max(f[j],f[j-k*c[i]]+k*w[i]);

分组背包

reference 的写法好像错了，这里提出一个貌似正确的写法（错了求轻喷
用了链式前向星来存储qwq

    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i]>>gp;
        if(head[gp]==-1) g[++gtot]=gp;
        nxt[i]=head[gp];
        head[gp]=i;
    }
    for(int i=1;i<=gtot;i++){
        for(int j=m;j>=0;j--){
            int p=head[g[i]];
            while(p!=-1){
                if(j>=v[p]) f[i][j]=max(f[i-1][j],f[i-1][j-v[p]]+w[p]);
                else f[i][j]=f[i-1][j];
                p=nxt[p];
            }
        }
    }

或者直接一维数组

for(int i=1;i<=gtot;i++){
        for(int j=m;j>=0;j--){
            int p=head[g[i]];
            while(p!=-1){
                if(j>=v[p]) f[j]=max(f[j],f[j-v[p]]+w[p]);
                p=nxt[p];
            }
        }
    }

二进制拆分

易得，我们可以把一个数拆成若干个2的幂以及一个不是2的幂的数（也有可能没有）,
选择这些数的其中一些数求和可以得到 1 ~ 这个数的任意一个
我也不知道为什么可以啊，好神奇

for(int i=1;i<=tot;i++)
    for(int j=V;j>=0;j--){
        for(int k=1;k<=num[i];k++){
            int power=1;
            while(x>=power){
              x-=power;
              c_n[tot]=c[i]*power;
              w_n[tot++]=w[i]*power;
              power<<=1;
            }
        }
        if(j-k*c_n[i]>=0) f[j]=max(f[j],f[j-k*c_n[i]]+k*w_n[i]);
    }