背包问题

AcWing 2. 01背包问题

1
2
3
4
5
6
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int v[N], w[N], f[N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    cout << f[m] << endl;
    
    return 0;
}

对f[i]有影响的只有f[i-1]，所以为了避免用更新过的f[i-1]来更新f[i]，我们的代码是从大到小来更新

AcWing 3. 完全背包问题

跟0-1背包问题的区别是：01背包问题，一个物品只能选择一次，为了用更新过的f[i-1]来更新f[i]，0-1背包问题从大到小更新。

而完全背包问题可以选择无限次，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N], f[N];  // v[i] 体积, w[i] 价值, f[j] 表示容量为 j 时的最大价值

int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )  // j可以从0开始，但是f[j - v[i]]下标会变成负数
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            
    printf("%d", f[m]);
    
    return 0;
}

第 i 件物品 可以选多次，所以要从 小到大遍历 j，保证 f[j - v[i]] 已经计算的是本轮更新后的 f[j - v[i]]，即包含了重复选物品的可能。

AcWing 4. 多重背包问题（一）

多重背包问题也是0-1背包问题的一个变式。与 0-1 背包的区别在于每种物品有 ki个，而非一个。
注意：完全背包问题是每种物品无限个。

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
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m;   // n: 物品数量，m: 背包容量
int v[N], w[N], s[N];  // v[i]: 体积，w[i]: 价值，s[i]: 数量上限
int f[N][N];    // f[i][j]: 只前 i 个物品，容量为 j 时的最大价值

int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ ) scanf("%d%d%d", &v[i], &w[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 * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
                
    printf("%d", f[n][m]);
    
    return 0;
}

每次都枚举当前体积为j的所有可能装法；有条件限制，不会想完全背包问题一样出现下标为负的问题

AcWing 5. 多重背包问题（二）

这里介绍的是多重背包问题的二进制优化，将一个最多选 s 次的物品，拆成若干个 01背包问题中的物品。

核心思想是：

把一个数 s 拆成若干个 2 的幂的和：如 s = 13 拆成 1 + 2 + 4 + 6（其中最后一项是余数）

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
#include <bits/stdc++.h>

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    scanf("%d%d", &n, &m);
    
    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;   // a:体积, b:价值, s:最大数量
        scanf("%d%d%d", &a, &b, &s);
        
        int k = 1;
        while (k <= s)
        {
            cnt ++ ;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;   // s 是总数，每次都减去k，那么就是剩下的了
            k *= 2;   // k从最小幂次开始   2  4  8 ... 反正不会越界
        }
        // 这里就是补足剩下的东西了   再进行计算
        if (s > 0)
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    
    n = cnt ;
    // 上面已经拆分成0-1背包问题了，物品都是独一无二的了，直接套用01背包代码即可
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    printf("%d", f[m]);
    
    return 0;
}

🔢 举个例子：s = 13

拆分轮次 k值 s剩余 体积 v[cnt] 价值 w[cnt]
初始 1 13 a×1 b×1
第1轮 2 12 a×2 b×2
第2轮 4 10 a×4 b×4
第3轮 8 6 ❌ 不满足 k <= s，跳出 while

还剩下 s = 6，需要补一个：

1
2
3
4
5
6
if (s > 0)
{
    cnt ++;
    v[cnt] = a * s;
    w[cnt] = b * s;
}

最终拆成了：1件、2件、4件、6件（总共13件 ✅） 每件价值 体积都不一样， 化简为01背包问题了

AcWing 9. 分组背包问题

题目描述：有n组物品和一个大小为m的背包，第i个物品的价值为wi，体积为vi。同时，每个物品属于一个组，同组内最多选择一个物品（可以不选）。求背包能装载物品的最大总价值

思考：其实就是从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了。

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
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m;						// n：组数，m：背包容量
int v[N][N], w[N][N], s[N];		// v[i][k]：第 i 组第 k 个物品的体积，w[i][k] 是价值
int f[N];						// f[j]：容量为 j 时的最大价值

int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &s[i]);
        for (int j = 0; j < s[i]; j ++ )
            scanf("%d%d", &v[i][j], &w[i][j]);
    }
    
    for (int i = 1; i <= n; i ++ )  // 循环每一组
        for (int j = m; j >= 0; j -- )  //循环背包容量  从大到小
            for (int k = 0; k < s[i]; k ++ )   // 循环该组的每一个物品
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                    
    printf("%d", f[m]);
    
    return 0;
}