5. 多重背包问题 II(acwing)

5. 多重背包问题 II

题目描述

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

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

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

输出最大价值。

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

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

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

数据范围
0

0

0i,w_i,s_i≤2000

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

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2
1
2
3
4
5

输出样例：

10
1

动态规划

一维数组

三重循环（超时）

这段代码是用于解决多重背包问题的，它使用了动态规划（DP）的方法，并且通过二进制的思想对多重背包问题进行了优化。不过，请注意，这个代码并没有实际使用二进制优化，而是使用了一个普通的三重循环方法。下面我会注释这段代码，但也会提到二进制优化原理。

#include  // 包含了几乎所有常用的库
using namespace std;

// 定义三个数组，分别存储物品的体积、价值和数量
int v[1010], w[1010], s[1010];
// 定义一个一维数组dp，用于存储背包的容量与可达到的最大价值
int dp[2020];

int main()
{
    int n, m;  // n为物品种类，m为背包容量
    cin >> n >> m;  // 输入物品数量和背包容量
    for(int i=1; i<=n; i++)
        cin >> w[i] >> v[i] >> s[i];  // 输入每个物品的体积、价值和数量
    // 遍历每种物品
    for(int i=1; i<=n; i++)
        // 从背包容量开始向下遍历，这样可以确保每个物品只选择一次
        for(int j=m; j>=w[i]; j--)
            // 遍历可以选择的物品数量，注意不超过背包容量和物品数量限制
            for(int k=0; k<=s[i] && k*w[i]<=j; k++)
                // 更新dp[j]为不选择或选择k个第i种物品的最大值
                // dp[j-k*w[i]]+k*v[i]表示选择k个第i种物品的价值
                dp[j] = max(dp[j], dp[j-k*w[i]]+k*v[i]);
    // 输出背包容量为m时的最大价值
    cout << dp[m];
    return 0;
}
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

上面的代码是对多重背包问题的直观解决方法，在这种方法中，我们对于每种物品，都尝试从0件到s[i]件之间的所有可能性，并更新状态dp[j]。这是一种朴素的方法，动态规划状态转移方程如下：

dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i])，其中k是选择的第i种物品的数量，这个方程表示背包容量为j时最大价值可以是不选当前物品的价值dp[j]，或者选了k个当前物品的价值dp[j - k * w[i]] + k * v[i]。

尽管这个代码段没有使用二进制优化，但是二进制优化的思想是：将每种类型的物品数量按照二进制拆分，即将每种物品分解为1件、2件、4件…，2^{k件（其中2}k不超过s[i]），通过这种方式可以将多重背包问题转换为0/1背包问题来解决，从而优化时间复杂度。

这段代码是完整的，并且可以正确地解决多重背包问题，但在面对大数据集时可能不够高效，那时候二进制优化就显得非常必要了。在实际应用中，你可以根据数据的大小和时间复杂度要求，来决定是否使用二进制优化。

二进制优化（正确代码）

这段代码是多重背包问题的解决方案，使用了二进制优化方法。详细注释如下：

#include
using namespace std;

// 设置最大数组范围
const int z=25000;
// v数组保存每个拆分后的物品的价值，w数组保存每个拆分后的物品的体积
int v[z],w[z]; 
// dp数组用于动态规划，记录背包容量为j时可达到的最大价值
int dp[z]; 

int main()
{
    int n,m; // n为物品种数，m为背包容积
    cin>>n>>m; // 读入物品种数和背包容积
    int pos=0; // pos用于记录拆分物品的个数
    // 循环处理每种物品
    for(int i=1;i<=n;i++)
    {
        int a,b,s; // a为体积，b为价值，s为数量
        cin>>a>>b>>s; // 读入体积、价值、数量
        int k=1; // 用于二进制拆分，初始为2的0次方，即1
        // 当物品数量大于等于k时进行拆分
        while(k<=s)
        {
            // 按照二进制拆分原则，存储拆分后物品的体积和价值
            w[++pos]=a*k; // 拆分的体积是原体积的k倍
            v[pos]=b*k; // 拆分的价值是原价值的k倍
            // 减去已经拆分的数量
            s-=k;
            // k翻倍进行下一次二进制拆分
            k*=2;
        }
        // 如果还有剩余物品，则继续存储剩余的体积和价值
        if(s>0)
        {
            w[++pos]=a*s; // 剩余的体积
            v[pos]=b*s; // 剩余的价值
        }
    }
    // 使用一维数组的动态规划求解，类似于01背包问题
    for(int i=1;i<=pos;i++) // 遍历所有拆分后的物品
    {
        // 从大到小遍历背包容量，确保每个物品只被计算一次
        for(int j=m;j>=w[i];j--)
        {
            // dp[j]是不放这件物品，dp[j-w[i]] + v[i]是放这件物品
            // 更新dp[j]为这两者的较大值
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    // 输出背包容量为m时，能装入物品的最大价值
    cout<<dp[m];
    return 0;
}
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
47
48
49
50
51
52
53
54

在这个多重背包问题中，每种物品可以有多件，但是数量有限。二进制优化的思路是将每种物品拆分成若干个组合，使得每个组合内物品的数量是2的幂次，这样可以通过少量的组合来组成任意数量的物品，减少了状态的数量。优化后使用动态规划求解时，就如同解决01背包问题一样，每个物品只会被选取一次。最后输出的 dp[m] 就是所求的最大价值。

二维数组

三重循环（超时）

这段代码是一个解决多重背包问题的例子，它使用了动态规划的方法。具体来说，它利用二维动态规划数组dp[i][j]来存储考虑前i种物品，当背包容量为j时所能达到的最大价值。下面是对这段代码的详细注释：

#include // 包括STL库
using namespace std;

// 定义数组，v[i]、w[i]和s[i]分别存储第i种物品的体积、价值和数量。
int v[1010], w[1010], s[1010];
// dp[i][j]表示考虑前i种物品，当背包容量为j时的最大价值。
int dp[2020][2020];

int main()
{
    int n, m; // n是物品种数，m是背包容量
    cin >> n >> m; // 输入物品种数和背包容量
    // 读入每种物品的体积v[i]、价值w[i]和数量s[i]
    for(int i = 1; i <= n; i++)
        cin >> w[i] >> v[i] >> s[i];

    // 动态规划求解
    for(int i = 1; i <= n; i++) // 遍历所有物品
    {
        for(int j = 0; j <= m; j++) // 遍历所有可能的背包容量
        {
            for(int k = 0; k <= s[i] && k * w[i] <= j; k++) // 遍历当前物品可以选择的数量，确保不超过该物品的数量限制且背包容量不会超标
            {
                // dp[i][j]更新为考虑当前i种物品、容量为j时的最大价值
                // max函数比较不取当前物品的情况和取k个当前物品情况下的价值，选择较大者
                dp[i][j] = max(dp[i][j], dp[i-1][j-k*w[i]] + k*v[i]);
            }
        }
    }
    // 输出考虑n种物品，背包容量为m时的最大价值
    cout << dp[n][m];
    return 0;
}
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

动态规划原理解释

这个动态规划的过程是按照物品的种类进行的，对于每一种物品i，它都会尝试从0件到s[i]件进行选择，并更新状态dp[i][j]。这里的dp[i][j]代表考虑到第i种物品时，背包容量为j能够达到的最大价值。

• dp[i-1][j-k*w[i]] + k*v[i]的意思是，如果当前考虑选择k个第i种物品，那么背包里剩余的容量为j-k*w[i]，对应的最大价值是dp[i-1][j-k*w[i]]（即在没有考虑第i种物品时的最大价值），再加上k个第i种物品的价值k*v[i]。

这种方法遍历了物品的每种可能性，确保找到在不超过背包容量的情况下，物品的最大总价值。通过更新dp[i][j]，最终dp[n][m]存储的就是在考虑所有n种物品，且背包容量为m时的最大价值。

二进制优化（超出内存限制）

下面是代码的详细注释，解释了每一部分的作用和实现的功能：

#include
using namespace std;

// 定义最大的数组范围
const int z=8000;
// 定义价值和重量数组
int v[z],w[z];
// 定义动态规划的数组，dp[i][j]表示前i件物品在不超过j体积时的最大价值
int dp[z][z];

int main()
{
    // n 表示物品种类数，m 表示背包的容量
    int n,m;
    cin>>n>>m;
    // pos 用于记录当前拆分后的物品的个数
    int pos=0;
    
    // 遍历每种物品
    for(int i=1;i<=n;i++)
    {
        // a 表示每件物品的体积，b 表示每件物品的价值，s 表示物品的数量
        int a,b,s;
        cin>>a>>b>>s;
        int k=1; // k 用于表示当前拆分的物品件数，初始为1，即2^0

        // 二进制拆分物品
        while(k<=s)
        {
            // 拆分物品加入数组，体积和价值都按照拆分的件数k倍增
            w[++pos]=a*k;
            v[pos]=b*k;
            // 减去已经拆分的物品数量
            s-=k;
            // 更新 k 为下一次拆分的件数，即翻倍
            k*=2;
        }
        // 如果还有剩余未拆尽的物品，则继续拆分剩下的
        if(s>0)
        {
            w[++pos]=a*s;
            v[pos]=b*s;
        }
    }

    // 动态规划处理每个物品
    for(int i=1;i<=pos;i++)
    {
        // 遍历背包的容量
        for(int j=0;j<=m;j++)
        {
            // 不选第i件物品的情况，价值等同于没有第i件物品时的价值
            dp[i][j]=dp[i-1][j];
            // 选第i件物品的情况，只有当背包容量足够时考虑
            if(j>=w[i])
                // 选和不选的最大值
                dp[i][j]=max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
        }
    }

    // 输出所有物品处理完后，背包容量为m时的最大价值
    cout<<dp[pos][m];
    
    return 0;
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

这段代码的主要目的是通过二进制拆分将多重背包问题转化为01背包问题，并利用动态规划求解。二进制拆分是一种优化手段，它通过拆分物品数量来减少状态转移的次数，这在处理多重背包问题时非常有效。在动态规划阶段，由于物品已经被拆分，代码实际上是在按照01背包问题的方式处理每件物品。最后通过动态规划数组 dp 来得出最大价值。