DP-四种背包问题模板总结【01背包、完全背包、多重背包、混合背包】

首先区分四种背包的概念：

01背包：有N件物品和一个容量为V的背包。每种物品均只有一件。 第i件物品的质量是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的质量总和不超过背包容量，且价值总和最大。
完全背包：有N种物品和一个容量为V的背包。每种物品都有无限件可用。 第i件物品的质量是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的质量总和不超过背包容量，且价值总和最大。。
多重背包：有N种物品和一个容量为V的背包。第i种物品最多有s[i]件可用， 每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的质量总和不超过背包容量，且价值总和最大。
混合背包： 有N种物品和一个容量为V的背包。有的物品只可以取一次(01背包)，有的物品可以取无限次(完全背包)，有的物品可以取的次数有一个上限(多重背包)。 求解将哪些物品装入背包可使这些物品的质量总和不超过背包容量，且价值总和最大。
比较四种背包，会发现不同点在于每种背包的数量，01背包是每种只有一件，完全背包是每种无限件，多重背包是每种有限件，而混合背包是前三种背包的混合。

洛谷 P1048 采药（01背包）

这题是01背包的模板题，开一个dp数组，dp[i]表示装入物品的质量为i时能获得的最大价值。
注意把dp数组开大一点(要开到物品数的十倍)，虽然最多不超过100个物品，但是开到200都会RE…

#include <bits/stdc++.h>
using namespace std;
int n,v,w,c,dp[1010];//dp[i]表示装入物品的质量为i时能获得的最大价值
int main()
{
    cin>>v>>n;//v为背包容量，n为物品数量
    for(int i=1;i<=n;i++)
    {
        cin>>w>>c;//w为每个物品重量，c为每个物品价值
        for(int j=v;j>=w;j--)//背包容量从大到小遍历
        dp[j]=max(dp[j],dp[j-w]+c);//选择不放入背包dp[j]还是放入背包dp[j-w]+c，更新为最大的dp[j]
    }
    printf("%d\n",dp[v]);//装入物品的质量为v时能获得的最大价值
    return 0;
}

洛谷 P1616 疯狂的采药（完全背包）

这题是完全背包的模板题，注意01背包的第二层循环是 for(int j=v;j>=w;j--) ，
而完全背包的第二层循环是 for(int j=w;j<=v;j++)，与01背包循环顺序相反。

#include <bits/stdc++.h>
using namespace std;
int n,v,w,c,dp[100010];
int main()
{
    cin>>v>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w>>c;
        for(int j=w;j<=v;j++)//背包容量从小到大遍历，这里与01背包循环顺序相反！
        dp[j]=max(dp[j],dp[j-w]+c);
    }
    printf("%d\n",dp[v]);
    return 0;
}

nefu 1271 多重背包

多重背包可以转化为01背包求解，可以把每次输入的s件物品分解为2的幂次和，
比如说s=7，那么s=1+2+4，相应地就把多重背包转化为
w[1]=1 * w0，c[1]=1 * c0，
w[2]=2 * w0，c[2]=2 * c0，
w[3]=4 * w0，c[3]=4 * c0，
这就是所谓的多重背包的二进制优化。
当然你也可以把s件一件一件的分解(s=1+1+…+1)，用这种朴素的做法，数据大就容易超时，不推荐使用。

#include <bits/stdc++.h>
using namespace std;
int n,v,s,k,w0,c0,cnt,rest,w[100010],c[100010],dp[100010];
int main()
{
    cin>>n>>v;
    while(n--)
    {
        cin>>w0>>c0>>s;//重量为w0，价值为c0的物品有s件
        rest=s;k=1;//rest是剩余的物品数，k是从小到大的2的幂次
        while(rest>=k)//rest<k时结束，结束时按2的幂次恰好分完则rest=0，否则0<rest<k，要继续处理剩余的rest
        {
            w[++cnt]=w0*k;
            c[cnt]=c0*k;
            rest=rest-k;
            k=k*2;
        }
        if(rest>0){w[++cnt]=w0*rest;c[cnt]=c0*rest;}
    }
    for(int i=1;i<=cnt;i++)
        for(int j=v;j>=w[i];j--)
            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
    printf("%d\n",dp[v]);
    return 0;
}

nefu 1715 混合背包

混合背包：有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。
这样看来混合背包其实就是01背包+多重背包+完全背包，而多重背包又可以转化为01背包，
所以要解决混合背包的问题可以分别按多重背包和完全背包的方式处理。

#include <bits/stdc++.h>
using namespace std;
int n,v,s,k,w0,c0,cnt,rest,w[100010],c[100010],dp[100010];
int main()
{
    cin>>v>>n;
    while(n--)
    {
        cin>>w0>>c0>>s;//重量为w0，价值为c0的物品有s件
        if(s==0)//按完全背包处理
        {
            for(int j=w0;j<=v;j++)
            dp[j]=max(dp[j],dp[j-w0]+c0);
        }
        else//把多重背包转化为01背包，把s分解为2的幂次和，保存到w数组和c数组中，之和再按01背包处理
        {
            rest=s;k=1;//rest是剩余的物品数，k是从小到大的2的幂次
            while(rest>=k)//rest<k时结束，结束时按2的幂次恰好分完则rest=0，否则0<rest<k，要继续处理剩余的rest
            {
                w[++cnt]=w0*k;
                c[cnt]=c0*k;
                rest=rest-k;
                k=k*2;
            }
            if(rest>0){w[++cnt]=w0*rest;c[cnt]=c0*rest;}
        }
    }
    for(int i=1;i<=cnt;i++)//按01背包处理
        for(int j=v;j>=w[i];j--)
            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
    printf("%d\n",dp[v]);
    return 0;
}

———————————————————————————————————————————————

如果把背包改一下，容量不固定了，改成求大于等于容量V的最小花费，怎么做呢？我们看看这题：洛谷 P2918 买干草 (改编完全背包)

这题注意，总质量是可以大于v的，关键在于如何使花费最小，那么质量可以大一点，所以第二重循环的结束点不应该在v，而应该在v+5000(因为物品最大质量是5000)。此时dp[i]表示质量达到i时的最小花费。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,v,w,c,ans,dp[100010];//dp[i]表示质量达到i时的最小花费
int main()
{
    cin>>n>>v;ans=inf;
    for(int i=1;i<=v+5000;i++)
        dp[i]=inf;//dp初始化
    for(int i=1;i<=n;i++)
    {
        cin>>w>>c;
        for(int j=w;j<=v+5000;j++)//结束位置在v+5000而不是5000
        dp[j]=min(dp[j],dp[j-w]+c);
    }
    for(int i=v;i<=v+5000;i++)//从大于等于v时开始找最小dp值
        ans=min(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}