大家都知道的多重背包与混合背包

多重背包

• 多重背包1
• • 原题链接
  • 问题
  • 分析
  • 程序
• 多重背包2
• • 来源
  • 题目
  • 分析
  • 程序
• 混合背包
• • 题目来源
  • 题目
  • 分析
  • 程序

多重背包1

原题链接

https://www.acwing.com/problem/content/4/

问题

分析

与01背包不同的是，多重背包的每一个物品有S件，而01背包每个物品有1件。

我们是不是可以进行一个拆分，把这S件物品拆成01背包的模型来计算。

我们再看物品的数量，假设最多的100件物品，每个物品可以取100次，我们使用三重循环的话，时间复杂度是

100 * 100 * 100

，也就是

10的6次方

。而C++程序一秒大概可以执行

10的7次方 ~ 10的8次方左右

的次数。

也就是说我们简单使用三重循环的暴力方法是可以过的。

程序

#include <iostream>
using namespace std;

const int N = 110;

int dp[N];
int n,m;

int main()
{
    cin>>n>>m;
    
    for(int i = 1; i <= n; i++)
    {
        int v,w,s;//v 物品所占的体积 w 物品的重量 s 物品的数量
        cin>>v>>w>>s;
        
        for(int j = m; j >= v; j--)
            for(int k = 1; k <= s && (k * v <= j); k++)
                dp[j] = max(dp[j], dp[j - k * v] + k * w);
    }
    
    cout<<dp[m]<<endl;
    return 0;
}
           

多重背包2

来源

https://www.acwing.com/problem/content/5/

题目

分析

看了一眼数据范围，

1000 * 2000 * 2000

，直接暴力三重循环肯定超时了。

提示中显示，可以使用二进制优化的方法，也就是使用二进制对背包进行压缩。

我们直接把所有物品都变成一个一个的肯定不行，我们可以利用二进制独特的压缩方式，可以把多个物品压缩成一个物品，这样物品的数量压缩的范围简化到

1000 * log(2000)

，时间复杂度近似于

1000 * 11 * 2000

，我们看这是可以在1S 中跑完的，时间复杂度可以通过了。

程序

#include <iostream>
#include <vector>
using namespace std;

const int N = 2010;

int n,m;
int dp[N];
//存放压缩后物品的仓库
typedef struct Good
{
    int v,w;
}Good;

int main()
{
    cin>>n>>m;
    vector<Good> goods;
    
    for(int i = 1; i <= n; i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        //状态压缩
        //10 -> 1 + 2 + 4 + 3
        for(int k = 1; k <= s; k *= 2)
        {
            goods.push_back({v*k, w*k});
            s -= k;
        }
        //不能分解的，单独构成一个物品
        if(s) goods.push_back({v*s, w*s});
    }
    //安装01背包的模板进行遍历
    for(int i = 0; i < goods.size(); i++)
        for(int j = m; j >= goods[i].v; j--)
            dp[j] = max(dp[j], dp[j - goods[i].v] + goods[i].w);
    
    cout<<dp[m]<<endl;
    return 0;
}
           

混合背包

题目来源

https://www.acwing.com/problem/content/7/

题目

分析

我们可以看到，在这个题中，一个物品有三种类型，一种可以使用1次(01背包)，一种可以使用无限次(完全背包)，最后一种可以使用多次(多重背包)。

而且时间复杂度也是挺高的，

1000 * 1000 * 1000

，10的9次方，已经超过了C++1秒的执行次数。

和上面的多重背包问题相同，我们可以采用压缩的方式，将多重背包都利用二级制的思想压缩为01背包，然后分情况来解决混合背包的问题。我们就把题目变成了01背包和完全背包的情况。

时间复杂度

1000 * 11 * 1000 + 1000 * 1000

，这是完全可以的。

程序

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 10010;

struct Good
{
  int s;//物品的类别
  int v,w;// 物品的体积，重量
};

vector<Good> goods;
int dp[N];

int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i = 1; i <= n; i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        
        //分类
        if(s <= 0) goods.push_back({s,v,w}); 
        else
        {
            //多重背包分解
            for(int k = 1; k <= s; k *= 2)
            {
                goods.push_back({-1,k*v,k*w});
                s -= k;
            }
            if(s) goods.push_back({-1,s*v,s*w});
        }
    }
    
    //计算
    for(int i = 0; i < goods.size(); i++)
        if(goods[i].s == -1)//01背包
            for(int j = m; j >= goods[i].v; j--)
                dp[j] = max(dp[j], dp[j - goods[i].v] + goods[i].w);
        else                //多重背包问题
            for(int j = goods[i].v; j <= m; j++)
                dp[j] = max(dp[j], dp[j - goods[i].v] + goods[i].w);
    
    cout<<dp[m]<<endl;
    return 0;
}