混合背包

题目描述

有\(N\)种物品和一个容量是\(V\)的背包。物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用\(s_i\)次（多重背包）；

每种体积是\(v_i\)，价值是\(w_i\)。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，\(N,V\)表示物品种数和背包容积。

接下来有\(N\)行，每行三个整数\(v_i,w_i,s_i\)，用空格隔开，分别表示第\(i\)种物品的体积、价值和数量。

\(s_i=−1\)表示第\(i\)种物品只能用\(1\)次；
\(s_i=0\)表示第\(i\)种物品可以用无限次；
\(s_i>0\)表示第\(i\)种物品可以使用\(s_i\)次；

数据范围

\(0<N,V≤1000\)，\(0<v_i,w_i≤1000\)，\(−1≤s_i≤1000\)

思路和代码1

混合背包就是将前面三种的背包问题混合起来，有的只能取一次，有的能取无限次，有的只能取\(k\)次。

先将01背包和完全背包转化成多重背包。

01背包，物品数量为1的多重背包，
完全背包，物品数量为\(V_{背包体积}/v_i\)的多重背包，虽然物品数量是无限的，但是背包容量是有限的。

再按照多重背包来做即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1005 * 20;
int f[N], w[N], v[N], n, m;
int main()
{
    int cnt = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        int a, b, s;
        cin >> a >> b >> s;
        if (s == 0) s = m / a;//如果是完全背包，则看成多重背包做
        if (s == -1)//01背包
        {
            cnt ++;
            v[cnt] = a, w[cnt] = b;
        }
        else//多重背包二进制拆分
        {
            int k = 1;
            while (k <= s)
            {
                cnt ++;
                v[cnt] = k * a;
                w[cnt] = k * b;
                s -= k;
                k *= 2;
            }
            if (s)
            {
                cnt ++;
                v[cnt] = s * a;
                w[cnt] = s * b;
            }
        }
    }
    for (int i = 1; i <= cnt; i ++)
        for (int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m];
    return 0;
}

思路和代码2

01背包当成数量为1的多重背包，然后进行二进制优化。

完全背包的求法与01背包不同，所以单独算完全背包部分。

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        if (!s)//完全背包
        {
            for (int j = v; j <= m; j ++)
                f[j] = max(f[j], f[j - v] + w);
        }
        else
        {
            if (s == -1) s = 1;//01背包当成数量为1的多重背包
            for (int k = 1; k <= s; k *= 2)
            {
                for (int j = m; j >= k * v; j --)
                    f[j] = max(f[j], f[j - k * v] + k * w);
                s -= k;
            }
            if (s)
            {
                for (int j = m; j >= s * v; j --)
                    f[j] = max(f[j], f[j - s * v] + s * w);
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}