背包型动态规划

背包问题也是动态规划中一个很经典的问题

其问题主要框架为：有一个体积为V的背包（花费上限），有n件物品，第i件物品的体积为v[i]，价值为w[i],问怎么放的最大价值。

当然，不同的题会对物品有不一样的限制，比如对物品数量的限制，对物品关系的限制，因此就有了不同种类的背包问题。

---

一，01背包

问题：有一个体积为V的背包，有n件物品，第i件物品的体积为v[i],价值为w[i]，每件物品至多选择一次，问在不超过背包体积的前提下能获得的最大价值。

这是背包型动态规划的基础，有些背包型动态规划可以转化为01背包，从而起到优化的效果。

特点是对于第i件物品，我们只有两种选择，第一种，将这件物品放入背包，第二种，不放这种物品，显然，我们想要在当前体积限制下获得最大的价值，如果

放入这件物品会使总的价值增大，我们就放入这件物品，否则不放。

状态转移方程 dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]+c[i]]);

for(int i=1;i<=n;i++)
    for(int v=1;v<=vmax,v++)
    {
        if(w[i]>v) dp[i][v]=dp[i-1][v];
        else dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
     }

我们可以通过数组的重复利用优化掉一维，从而在空间上优化了01背包。

注意一维的01背包的体积需要倒叙枚举，因为每个物品只能使用一次，如果正序枚举，可能导致某一个体积的最大价值是由这件物品已经更新过的

最大价值转移而来，从而导致了重复放该件物品。

for(int i=1;i<=n;i++)
    for(int v=vmax;v>=w[i];v--)
        dp[v]=max(dp[v],dp[v-w[i]]+c[i]);

---

二，完全背包

问题：有一个体积为V的背包，有n件物品，第i件物品的体积为v[i],价值为w[i]，每件物品至多选择无数，问在不超过背包体积的前提下能获得的最大价值。

我们刚刚在将01背包从二维优化到一维的时候讨论过体积必须倒叙枚举的问题，为什么呢，因为为了防止重复放，而完全背包允许重复放，所以改成正序枚举即可。

状态转移方程 dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i]);

for(int i=1;i<=n;i++)
    for(int v=w[i];v<=vmax;v++)
        dp[v]=max(dp[v],dp[v-w[i]]+c[i]);

一个贪心的小技巧：因为完全背包对于物品数没有限制，所以对于某两件物品i,j，如果w[i]<=w[j],c[i]>=c[j];这样的物品j我们可以丢掉，因为显然i物品

比较物美价廉，在任何情况下，选择i物品都要优于选择j物品，因为它的花费小，奉献的价值还更大，对于随即数据，这种优化方法很有效。

---

三，多重背包

问题：有一个体积为V的背包，有n件物品，第i件物品的体积为v[i],价值为w[i]，件数为t[i]，问在不超过背包体积的前提下能获得的最大价值。

首先想一个暴力的做法，我们更改一下01背包，只需要再加一层循环枚举一下件数，是不是就可以解决这个问题。

暴力的状态转移方程：dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]*k]+k*c[i],1<=k<=t[i]);

for(int i=1;i<=n;i++)
    for(int v=1;v<=vmax;v++)
    {
        if(w[i]>v) dp[i][v]=dp[i-1][v];
        else
        {
            for(int k=1;k<=t[i];k++)
                dp[i][v]=max(dp[i-1][v],dp[i-w[i]*k]+k*c[i]);
        }
    }

同样，这种写法也可以优化成一维

for(int i=1;i<=n;i++)
    for(int v=vmax;v>=0;v--)
        for(int k=1;k<=t[i]&&k*w[i]<=vmax;k++)
            dp[v]=max(dp[v],dp[v-w[i]*k]+c[i]*k);

因为多了一层循环，所以在时间复杂度上，这种暴力的多重背包必然不优，我们可以用两种方法来优化多重背包。

1，二进制优化

原理：2^k（0<=k,k为整数）可以表示出任何正数。

所以我们将已知的第i件物品有t[i]件，拆分成第i件物品有log(t[i])件，这样在跑01背包的时候，物品自己就会凑起来，

比如某物品有三件，我们就拆分其中一件（2^0）为第一件这个物品，其中两件物品为第二件这个物品（2^k），这样如果

这件物品选几件最优在跑01背包的时候都能选出来。

for(int i=1;i<=n;i++)
{
    for(int k=1;k<=t[i];k=k<<1)
    {
        t[i]-=k;
        w[++cnt]=a[i]*k;
        c[++cnt]=b[i]*k;
    }
    if(t[i])
    {
        w[++cnt]=a[i]*t[i];
        c[++cnt]=b[i]*t[i];
    }
}
for(int i=1;i<=cnt;i++)
    for(int v=vmax;v>=w[i];v--)
        dp[v]=max(dp[v],dp[v-w[i]]+c[i]);

 注意：二进制优化左右用的不是一个数组，不然会引起数据冲突。

2，单调队列优化

咕咕咕，刚学的比较乱，等着再写

---

四，混合三种背包

所谓混合三种背包，就是物品有三种类型，一种只能选一件（01），一种有数量限制只能最多选t[i]件（多重背包），还有

一种物品可以选择无数件（完全背包），在做的时候，我们只需要判断属于那种背包然后跑就好。

for(int i=1;i<=n;i++)
{
    if(完全背包) 
    {
        for(int j=c[i];j<=V;j++)
            f[j]=max(f[j],f[j-c[i]]+w[i]);
    }
    else if(01背包) 
    {
        for(int j=V;j>=c[i];j--)
            f[j]=max(f[j],f[j-c[i]]+w[i]); 
    }
    else//否则就是完全背包了 
    {
        for(int j=V;j>=0;j--)
            for(int k=1;k<=num[i];k++)
                if(j-k*c[i]>=0)
                    f[j]=max(f[j],f[j-k*c[i]]+k*w[i]);
    }
}

可以应用上述优化策略。

---

六，二维费用背包

问题：比01背包增加了一个限制条件，比如总体积不能超过vmax,总重量不能超过mmax，只需要增加一维枚举即可，

注意01正序，完全倒叙，多重转化为01后倒叙。

代码懒得写了

---

七，分组背包

问题：就是有K组物品，每组只能选择一种物品，求最大价值。

是01背包的一种变种，我们只需要在第一微枚举组别，第二维枚举体积，第三维枚举该组的物品即可。

为什么不先枚举该组的物品再枚举体积呢？因为每组只能选择一件物品，试想一下，如果这样枚举，

在枚举到第二件物品的时候，所有的体积v都已经被第一件物品转移过了，如果再次转移，就会出现

选择多件的情况。

注意：分组背包是01背包的变种，所以体积需要倒叙枚举。

for(int i=1;i<=k;i++)
    for(int v=vmax;v>=0;v--)
        for(int j=1;j<=size[i];j++)
            if(w[i][k]<=v) dp[v]=max(dp[v],dp[v-w[i][k]]+c[i][k]);

---

八，有依赖的背包问题

就是物品之间产生了依赖关系，如果想要选择第j件物品（附件），必须选择第i件物品（主件）。

这种主件和附件的关系是从NOIP2006金明的预算方案开始的毒瘤毒瘤

对于这类题目的做法

我们先考虑有几种选法，我们可以选择一件主件，1,2,3,4....件附件，这是很显然的。

咕咕咕，以后再写。

---

九，背包方案总数

就是把取max的操作改成加法。

状态转移方程：f[i][v]=f[i-1][v]+f[i-1][v-w[i]];

---

NOIP情况不明，在此祝各位OIER在2019取得好成绩 RP++ SCORE++