python

5.4 KiB

Raw Permalink Blame History Unescape Escape

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 5. 多重背包问题 II

一、题目描述

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 s_i 件，每件体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。

输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

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

输出格式 输出一个整数，表示最大价值。

数据范围 0<N≤1000 0<V≤2000 0<v_i,w_i,s_i≤2000

提示：本题考查多重背包的二进制优化方法。

输入样例

输出样例：

二、与多重背包问题 `I` 的区别

区别在于数据范围变大了：现在是三个循环数据上限分别是1000(物品种数),2000(背包容积),第i种物品的体积、价值和数量的上限也是2000,原来的每个数字上限都是100！

解法I使用的是三重循环，计算次数就是 1000 * 2000 * 2000=4000000000=4 * 1e9 =40亿次

C++一秒可以算1e8次，就是1亿次，40亿肯定会超时!

三、二进制优化

Q:怎么来优化呢？ 答：我们先来思考一下为什么方法一的速度慢,因为三层循环: ① 第一层遍历每个物品 ② 第二层遍历每个可用的空间 ③ 第三层枚举当前物品使用了几个

Q:我们最终的目标是什么? 答：每个物品选择了几个才是最优的，价值最大的。

办法 用二进制思想把所有可能的组合都表示出来，转化为01背包问题！

假如A物品，有10个，你最后要几个不一定，可能是0个，1个,2个，....，10个。

我们可以这样打包：

上面这样的转化，就是把一个个尝试，转化为了成批说事，比如上面圆圈里的4，理解为i物品4个打成一包,体积是原来的4倍，价值也是原来的4倍。这个打包完成的新物品，你可以选择，也可以不选择，当你最终方案中i物品要了5个时，这个打包4就被选中了，当你最终方案中i物品要了2个时，这个打包4就被放弃了。

打包，就是成批讨论，避免了一个个讨论，组团，按yxc的说法就是集合，不管怎么样吧，二进制打包法将极大加快计算速度！理由：比如INT\_MAX,其实就是2^{31},也就是划分成了最多31个包，能不快吗！就是打包费点劲。

三、一维实现代码【推荐】

#include <bits/stdc++.h>
using namespace std;

const int N = 1010; // 个数上限
const int M = 2010; // 体积上限
int n, m, idx;
int f[M];

/*
Q:为什么是N*12?
A:本题中v_i<=2000,因为c数组是装的打包后的物品集合，每类物品按二进制思想，2000最多可以打log2(2000)+1个包，即　10.96578+1=12个足够,
同时，共N类物品，所以最大值是N*12。

如果题目要求v_i<=INT_MAX,那么就是log2(INT_MAX)=31,开31个足够,因为31是准确的数字，不需要再上取整。
为保险起见，可以不用计算数组上限，直接N*32搞定！
*/
struct Node {
    int w, v;
} c[N * 12];

int main() {
    cin >> n >> m;

    // 多重背包的经典二进制打包办法
    for (int i = 1; i <= n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 1; j <= s; j *= 2) { // 1,2,4,8,16,32,64,128,...打包
            c[++idx] = {j * w, j * v};
            s -= j;
        }
        // 不够下一个2^n时，独立成包
        if (s) c[++idx] = {s * w, s * v};
    }
    // 按01背包跑
    for (int i = 1; i <= idx; i++)
        for (int j = m; j >= c[i].v; j--) // 倒序
            f[j] = max(f[j], f[j - c[i].v] + c[i].w);
    // 输出
    printf("%d\n", f[m]);
    return 0;
}

四、二维+滚动数组代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010; // 个数上限
const int M = 2010; // 体积上限
int n, m, idx;
// 无法使用二维数组，原因是因为分拆后N*31*M=31*1010*2010太大了，MLE了
// 所以，需要使用滚动数组进行优化一下，思想还是二维的
int f[2][M];

struct Node {
    int w, v;
} c[N * 31];

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 1; j <= s; j *= 2) { // 1,2,4,8,16,32,64,128,...打包
            c[++idx] = {j * w, j * v};
            s -= j;
        }
        // 不够下一个2^n时，独立成包
        if (s) c[++idx] = {s * w, s * v};
    }

    // 按01背包跑就可以啦
    for (int i = 1; i <= idx; i++)
        for (int j = 1; j <= m; j++) {
            f[i & 1][j] = f[i - 1 & 1][j];
            if (j >= c[i].v)
                f[i & 1][j] = max(f[i & 1][j], f[i - 1 & 1][j - c[i].v] + c[i].w);
        }

    // 输出
    printf("%d\n", f[idx & 1][m]);
    return 0;
}

5.4 KiB Raw Permalink Blame History Unescape Escape