最大价值

01背包 多重背包 T3

4877. 最大价值 - AcWing题库

AcWing,第96场周赛

有一个容量为 $n$ 的背包和 $m+1$ 种物品，每种物品都有无限多个。

物品种类编号为 $0\sim m$。

第 $i$ 种物品的体积为 $v_i$，价值为 $w_i$。

在使用背包装入物品时，每种物品的限重如下：

• 第 $0$ 种物品：重量忽略不计，在装入时没有重量限制。
• 第 $1\sim m$ 种物品：第 $i$ 种物品的单个重量为 $h_i$，如果该种物品的装入总重量超过 $l_i$，则视为超重。

现在，请你挑选物品装入背包，要求

• 所有装入物品的总体积不得超过背包容量。
• 所有存在重量限制的物品均不得超重。
• 满足以上所有条件的前提下，所有装入物品的总价值尽可能大。

输出总价值的最大可能值。

注意审题，不要将 $n,m$ 的含义弄混。

输入格式

第一行包含四个整数 $n,m,v_0,w_0$。

接下来 $m$ 行，每行包含四个整数 $l_i,h_i,v_i,w_i$。

输出格式

一个整数，表示总价值的最大可能值。

数据范围

前 $4$ 个测试点满足 $1\le n\le 100$，$1\le m\le 2$。
所有测试点满足 $1\le n\le 1000$，$1\le m\le 10$，$1\le l_i,h_i,v_i,w_i\le 100$。

输入样例1：

10 2 2 1
7 3 2 100
12 3 1 10

输出样例1：

241

输入样例2：

100 1 25 50
15 5 20 10

输出样例2：

200

思路

有两个限制, 一个是体积-容量, 另一个是重量限制。并给了两种物品, 一种是忽略重量可以选择无限个（完全背包）, 另一种是选的数量不能超过对应的 $l$, 显然第二种就是每个物品选有限个（多重背包）。

算是 混合背包问题 的一个简化版。

先读入第一种物品, 然后用完全背包的方式处理掉, 接着读入第二种, 再用多重背包做一遍, 这样得出的f数组就是最后的答案。

也可以化为01背包, 第一种物品只有一个, 那么他最多选的个数不能超出容量, 把其复制对应份数, 再进行01背包也是可以得到正确结果。 多重背包的部分同理, 也可以化为01背包。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e4, M = 1e3 + 10;
int f[M];
int v[N], w[N], cnt;
 
int main()
{
    int n, m, v0, w0;
    cin >> m >> n >> v0 >> w0;
    for(int j = 0; j < m / v0; j++) v[cnt] = v0, w[cnt++] = w0;
    
    for(int i = 0; i < n; i++)
    {
        int l, h, v1, w1;
        cin >> l >> h >> v1 >> w1;
        for(int j = 0; j < l / h; j++)
            v[cnt] = v1, w[cnt++] = w1;
    }
    
    for(int i = 0; i < cnt; i++)
    {
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
    
    int res = 0;
    for(int i = 0; i <= m; i++) res = max(res, f[i]);
    cout << res << endl;
    
    return 0;
}