Lames's Blog

Acwing算法提高课-多重背包及其优化(4 & 5 & 6)

11/26/2022

# 多重背包及其优化问题

# 1.多重背包I (opens new window)

  1. 题目描述

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

    第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

  2. 思路

    和完全背包问题相同的思路，但和完全背包问题的不同之处在于，多重背包的 第i件物品的可选择数量有限

    • 状态转移方程
    /*
f[i][j] 表示考虑前 i 个物品，在体积为j的限制下的方案集合，f[i][j] = 方案中价值的最大值
*/
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i], ...... , f[i - 1][j - x * v[i]] + x * w[i])
// x = min(j / v[i], cnt[i]) , 既要考虑本身数量，也要考虑背包容积
    1
    2
    3
    4
    5

    • 状态初始化

      初始状态均为0，声明状态数组时已经默认初始化为0，无需再次初始化。

  3. 代码

    #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
const int V = 110;
int s[N];
int v[N];
int w[N];
int f[V];
int main()
{
    int n,vb;
    cin >> n >> vb;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i] >> w[i] >> s[i];
    }
    
    for (int i = 1; i <= n; i ++ )
    {
        for(int j = vb; j >= 0; j --)
        {
            int x = min(j / v[i], s[i]);
            while(x)
            {
                f[j] = max(f[j], f[j - x * v[i]] + x * w[i]);
                x --;
            }
        }
    }
    cout << f[vb] << endl;
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32

# 2.多重背包 II (opens new window)

  1. 题目描述

    题目描述同上，这里主要列一下数据范围

    0<N≤1000 0<V≤2000 0<vi,wi,si≤2000

    在极端情况下，数据计算量可达到 1000 * 2000 * 2000 即 2 * 10 ^9，在 1s 内会超时，故我们需要进行算法优化

  2. 思路

    已分析按照 题目1 思路做遇到极端数据会超时，所以我们需要对算法进行进一步的优化。

    经分析易知，我们需要找到价值最大的方案，其本质是枚举所有的方案，然后从中选出最优方案，即动态规划 问题完全可以使用暴力方法求解。但是不同的状态划分方式有着不同的时间复杂度，我们希望算法的复杂度尽可能小。

    考虑这样一种方式：

    ​ 对于第 i 个物品，其数量为 cnt[i] ，如果我们按照 1 2 4 .... 2 ^ n的形式将其划分不同的物品集合，然后将这一个物品集合看作一个物品，那么这样物品的个数可以得到进一步的压缩，但不会对最终的结果造成影响。假设某种选取方案选取了 x个物品i 那么，x 一定可以被 上述方案所划分的某几个集合所表示。可以用一句话总结，即 2^n次方可以表示任何一个数。

     这样来看，问题就转化为了对新划分物品的 0 1背包问题，即对每个物品有选 不选这两种选择。

    ​ 对于cnt[i] 可划分为 log2 cnt[i] + 1 个集合，log2 2000 = 11 ，即极端情况下需要划分为11 个集合，此时计算量大约为：

    ​ 1000 * 11 * 2000，完全不会超时。

    • 状态转移方程

      即为 0 1 背包问题的状态转移方程，问题的重点是转换为 0 1背包问题

    • 状态初始化

      参照 0 1背包问题的状态转移方程

  3. 代码

    #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 12010;
const int V = 2010;
int v[N];
int w[N];
int f[V];
int main()
{
    int n,vb;
    cin >> n >> vb;
    int a,b,c; // 读入体积、价值、数量
    int idx = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a >> b >> c;
        int num = 1;
        while(c - num >= 0)
        {
            c -= num;
            idx ++;
            v[idx] = num * a;
            w[idx] = num * b;
            num *= 2;
        }
        if(c)
        {
            idx ++;
            v[idx] = c * a;
            w[idx] = c * b;
        }
    }
    
    // 经上述过程处理之后，题目转换为 共有idx个物品，每个只能选一次的 0 1 背包问题
    for(int i = 1; i <= idx; i ++)
    {
        for(int j = vb; j >= v[i]; j --)
        {
            f[j] = max(f[j],f[j - v[i]] + w[i]);        
        }
    }
    
    cout << f[vb] << endl;
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46

# 3.多重背包III (opens new window)

  1. 题目描述

    0<N≤1000 0<V≤20000 0<vi,wi,si≤20000

    数据量进一步加大，需要进行进一步的优化

  2. 思路

    挖个坑，过几天填上......

  3. 代码

#

#