算法动态规划

背包问题拾遗

字数统计: 4.5k字   |   阅读时长: 20分
,

摘要: 背包问题的遗留问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 01背包和完全背包 和 01背包和完全背包题目汇总 中我们分别了解了 01 背包和完全背包的算法原理、代码模板，以及可以解决的组合问题。

本文我们看一下背包问题的一些遗留话题，首先是动态规划问题中偶尔会遇到的求最优决策方案数以及求具体的最优决策方案，这需要在动态规划的过程中维护一些额外信息。此外费用有时会遇到两个维度的情况，比如重量，体积。当一部分物品时 01 背包，另一部分物品满足完全背包时，称为混合背包问题，在 01 背包和完全背包的基础上，这种问题也是可以解决的。

总览：

$1 背包问题求方案数

求最优决策序列的方案数是 DP 问题的一种比较常规的后处理问题。求出 dp 信息之后对每个阶段的最优决策数用计数的乘法原理。

如果要用滚动数组压掉阶段这一维，需要开一个数组记录附加状态的各个值对应的最优方案数目。

11. 背包问题求方案数

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

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

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

输出 最优选法的方案数。注意答案可能很大，请输出答案模 1e9+7 的结果。

算法：01背包

  • 01 背包求最优决策序列方案数

状态定义以及初始化：

1
2
3
4
dp[j] := 容量为 j 的最大价值
dp[0] = 0, 其它初始化为负无穷
g[j] := 体积恰好为 j 的方案数
g[0] = 1

状态转移：

1
2
3
4
5
6
7
8
枚举物品 i, 枚举体积 j, 对应的方案数记为 s, 初始化 s = 0
1. 最优价值 t = max(dp[j], dp[j - v] + w)
2. 判断从哪边转移过来：
    若 dp[j] == t，则 s += g[j]
    若 dp[j - v] + w == t，则 s += g[j - v]
3. 取模的问题：若 s >= MOD，s -= MOD
4. dp[j] = t
5. g[j] = s

求出所有的 dp[j] 和 g[j] 后。先遍历 dp，求出最大价值，然后把 dp[i] 等于最大价值的 i 取出来，将其对应的 g[i] 加入到答案中

代码 (01 背包最优方案数)

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 <vector>
#include <iostream>
#include <climits>

using namespace std;

int main()
{
    int N;
    int V;
    int mod = 1e9 + 7;
    cin >> N >> V;
    vector<int> v(N, 0);
    vector<int> w(N, 0);
    for(int i = 0; i < N; ++i)
        cin >> v[i] >> w[i];
        
    vector<int> dp(V + 1, INT_MIN);
    vector<int> g(V + 1, 0);
    g[0] = 1, dp[0] = 0;

    for(int i = 1; i <= N; ++i)
        for(int j = V; j >= v[i - 1]; --j)
        {
            int s = 0;
            int t = max(dp[j], dp[j - v[i - 1]] + w[i - 1]);
            if(dp[j] == t) s += g[j];
            if(dp[j - v[i - 1]] + w[i - 1] == t) s += g[j - v[i - 1]];
            if(s >= mod) s -= mod;
            dp[j] = t;
            g[j] = s;
        }

    int maxw = 0;
    for(int i = 0; i <= V; ++i)
        maxw = max(maxw, dp[i]);

    int result = 0;
    for(int i = 0; i <= V; ++i)
        if(maxw == dp[i])
        {
            result += g[i];
            if(result > mod) result -= mod;
        }

    cout << result << endl;
    return 0;
}

$2 背包问题求具体方案

求具体的最优决策序列是 DP 问题的一种比较常规的后处理问题。求出 dp 信息之后，对每个阶段选择一个最优决策。

12. 背包问题求具体方案

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

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

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

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N 。

算法：01背包

01 背包问题求具体方案(字典序最小)。

代码(01 背包求具体最优决策序列方案)

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
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1, 0);
    vector<int> w(N+1, 0);

    for(int i = 0 ; i < N; i++)
        cin >> v[i] >> w[i];
        
    vector<vector<int> > dp(N + 1, vector<int>(V + 1, 0));

    for(int i = N; i >= 1; --i)
        for(int j = 0; j <= V; ++j)
        {
            dp[i - 1][j] = dp[i][j];
            if(j >= v[i - 1])
                dp[i - 1][j] = max(dp[i - 1][j], dp[i][j - v[i - 1]] + w[i - 1]);
        }
    // 以上 dp 枚举在 01 背包求最大价值上通过

    vector<int> result;
    int vol = V;
    for(int i = 1; i <= N; ++i)
    {
        if(vol - v[i - 1] >= 0 && dp[i - 1][vol] == dp[i][vol - v[i - 1]] + w[i - 1])
        {
            cout << i << " ";
            vol -= v[i - 1];
        }
    }

    return 0;
}

1449. 数位成本和为目标值的最大数字

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：

  • 给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
  • 总成本必须恰好等于 target 。
  • 添加的数位中没有数字 0 。

由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 “0” 。

提示：

1
2
3
cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000

示例 1：
输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出：”7772”
解释：添加数位 ‘7’ 的成本为 2 ，添加数位 ‘2’ 的成本为 3 。所以 “7772” 的代价为 23+ 31 = 9 。 “977” 也是满足要求的数字，但 “7772” 是较大的数字。
数字 成本
1 -> 4
2 -> 3
3 -> 2
4 -> 5
5 -> 6
6 -> 7
7 -> 2
8 -> 5
9 -> 5

示例 2：
输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出：”85”
解释：添加数位 ‘8’ 的成本是 7 ，添加数位 ‘5’ 的成本是 5 。”85” 的成本为 7 + 5 = 12 。

示例 3：
输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出：”0”
解释：总成本是 target 的条件下，无法生成任何整数。

示例 4：
输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出：”32211”

算法：完全背包

  • 完全背包
  • 求最大价值
  • 求字典序最大最有决策序列方案
1
2
3
4
5
6
7
8
9
dp[i][j] := 考虑 [0..i]，成本和为 j 时选出数位的数量最大值
答案 dp[n - 1][target]
初始化 dp[i][0] = 0, dp[i][1..target] = -1

转移
dp[i][j] = max(
        dp[i - 1][j]            i > 0
        dp[i][j - cost[i]] + 1  j - cost[i] >= 0 && dp[i][j - cost[i]] != -1
        )

用 dp 信息反推方案：

1
2
3
4
5
6
7
8
9
10
j = target
i = n
迭代 j:
    若 j - cost[i] >= 0 && dp[i][j - cost[i]] + 1 == dp[i][j]:
        说明当前 i 可选且能达到最优
        j -= cont[i]
        用 i 更新 result
    否则
        说明当前 i 不可选了，或者能选但不是最优
        --i

代码(完全背包求具体最优决策序列方案)

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
class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        int n = cost.size();
        vector<vector<int>> dp(n, vector<int>(target + 1, -1));
        for(int i = 0; i < n; ++i)
            dp[i][0] = 0;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 1; j <= target; ++j)
            {
                if(i > 0)
                    dp[i][j] = dp[i - 1][j];
                if(j - cost[i] >= 0 && dp[i][j - cost[i]] != -1)
                    dp[i][j] = max(dp[i][j], dp[i][j - cost[i]] + 1);
            }
        }
        if(dp[n - 1][target] == -1)
            return "0";
        string result;
        int i = 8;
        int j = target;
        while(j > 0)
        {
            if(j - cost[i] >= 0 && dp[i][j - cost[i]] + 1 == dp[i][j])
            {
                j -= cost[i];
                result += '0' + i + 1;
            }
            else
                --i;
        }
        return result;
    }
};

$3 二维费用

8. 二维费用的背包问题

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

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

输出最大价值。

代码 (二维费用01背包)

  • 二维费用01背包
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
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int N;
    int V;
    int M;
    cin >> N >> V >> M;
    vector<int> v(N, 0);
    vector<int> w(N, 0);
    vector<int> m(N, 0);
    for(int i = 0; i < N; ++i)
        cin >> v[i] >> m[i] >> w[i];
    
    vector<vector<int> > dp(V + 1, vector<int>(M + 1, 0));
    for(int i = 1; i <= N; ++i)
        for(int j = V; j >= v[i - 1]; --j)
            for(int k = M; k >= m[i - 1]; --k)
                dp[j][k] = max(dp[j][k], dp[j - v[i - 1]][k - m[i - 1]] + w[i - 1]);

    cout << dp[V][M] << endl;
    return 0;
}

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

提示：

1
2
3
4
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

示例 1：
输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,”1”} 和 {“10”,”1”,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：
输入：strs = [“10”, “0”, “1”], m = 1, n = 1
输出：2
解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

算法：01背包

  • 二维费用01背包
  • 所有物品价值均为 1

代码 (C++)

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
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        if(strs.empty()) return 0;
        int N = strs.size();
        int V1 = m, V2 = n; // 二维费用背包的两个容量

        vector<int> v1(N, 0); // 0 个数
        vector<int> v2(N, 0); // 1 个数
        for(int i = 0; i < N; ++i)
        {
            string str = strs[i];
            for(char c: str)
            {
                if(c == '0')
                    ++v1[i];
                else
                    ++v2[i];
            }
        }

        vector<vector<int> > dp(V1 + 1, vector<int>(V2 + 1, 0));
        for(int i = 0; i < N; ++i)
            for(int j = V1; j >= v1[i]; --j)
                for(int k = V2; k >= v2[i]; --k)
                    dp[j][k] = max(dp[j][k], dp[j - v1[i]][k - v2[i]] + 1);

        return dp[V1][V2];
    }
};

280. 陪审团

在一个遥远的国家，一名嫌疑犯是否有罪需要由陪审团来决定。

陪审团是由法官从公民中挑选的。

法官先随机挑选 N 个人（编号 1,2,…,N）作为陪审团的候选人，然后再从这 N 个人中按照下列方法选出 M 人组成陪审团。

首先，参与诉讼的控方和辩方会给所有候选人打分，分值在 0 到 20 之间。

第 i 个人的得分分别记为 p[i] 和 d[i]。

为了公平起见，法官选出的 M 个人必须满足：辩方总分 D 和控方总分 P 的差的绝对值 |D−P| 最小。

如果选择方法不唯一，那么再从中选择辨控双方总分之和 D+P 最大的方案。

求最终的陪审团获得的辩方总分 D、控方总分 P，以及陪审团人选的编号。

注意：若陪审团的人选方案不唯一，则任意输出一组合法方案即可。

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
输入格式：
输入包含多组测试数据。
每组测试数据第一行包含两个整数 N 和 M。
接下来 N 行，每行包含两个整数 p[i] 和 d[i]。
每组测试数据之间隔一个空行。
当输入数据 N=0，M=0 时，表示结束输入，该数据无需处理。

输出格式：
对于每组数据，第一行输出 Jury #C，C 为数据编号，从 1 开始。
第二行输出 Best jury has value P for prosecution and value D for defence:，P 为控方总分，D 为辩方总分。
第三行输出按升序排列的陪审人选编号，每个编号前输出一个空格。
每组数据输出完后，输出一个空行。

数据范围：
1<=N<=200,
1<=M<=20
0<=p[i],d[i]<=20

>输入样例：
>4 2
>1 2
>2 3
>4 1
>6 2
>0 0
>输出样例：
>Jury #1
>Best jury has value 6 for prosecution and value 4 for defence:
> 2 3

算法：01背包

  • 二维费用01背包
  • 后处理：求具体方案

每个人是物品：

第一维费用是人数，每个人都是 1，要求恰好取到 M。
第二维费用是控辩双方分差 diff
价值：控辩双方得分和

1
2
3
4
5
6
7
8
dp[i][j][k] := 前 i 个人选 j 个人，控辩双方总分差为 k 时的最大总分

初始化
dp[...][0][0] = 0
dp[...][...][...] = -INF

转移
dp[i][j][k] = max(dp[i-1][j][k], dp[i - 1][j - 1][k - (p[i] - d[i])] + p[i] + d[i])

分数范围 [0, 20]，20 个人总差值为 [-400, 400]，因此设偏移量 offset = 400，差值范围 [0, 800]

求出 dp 后在 dp 上后处理，首先找到最小的差值 diff，dp[n][m][offset - diff], dp[n][m][offset + diff] 较大的哪个作为最后一步的决策。然后往前倒推每一个阶段的决策。

代码 (C++)

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, M = 810, offset = 400;
int dp[N][21][M];
int d[N], p[N];

int main()
{
    int C = 1;
    int n, m;
    while(cin >> n >> m && !(n == 0 && m == 0))
    {
        for(int i = 1; i <= n; ++i)
            cin >> p[i] >> d[i];

        // dp 初始化
        memset(dp, -0x3f, sizeof(dp));
        dp[0][0][offset] = 0;

        // 求 dp
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 0; j <= m; ++j)
            {
                for(int k = 0; k < M; ++k)
                {
                    dp[i][j][k] = dp[i - 1][j][k]; // 不选 i
                    if(j == 0) continue;
                    int prev_diff = k - p[i] + d[i];
                    if(prev_diff < 0 || prev_diff > 800)
                        continue;
                    // i 可以选
                    if(dp[i - 1][j - 1][prev_diff] < 0)
                        continue;
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][prev_diff] + p[i] + d[i]);
                }
            }
        }

        // 后处理1 求 diff 以及最后一个阶段的决策
        int diff = 0;
        while(diff <= offset && dp[n][m][offset + diff] < 0 && dp[n][m][offset - diff] < 0)
            ++diff;
        if(dp[n][m][offset - diff] > dp[n][m][offset + diff])
            diff = offset - diff;
        else
            diff = offset + diff;

        // 倒推前面各个阶段的决策
        int i = n, j = m;
        vector<int> cand(m + 1);
        while(j > 0)
        {
            if(dp[i][j][diff] == dp[i - 1][j][diff])
                --i;
            else
            {
                cand[j] = i;
                diff -= (p[i] - d[i]);
                --i;
                --j;
            }
        }

        int tp = 0, td = 0;
        for(int i = 1; i <= m; ++i)
        {
            tp += p[cand[i]];
            td += d[cand[i]];
        }

        // 输出
        cout << "Jury #" << C++ << endl;
        cout << "Best jury has value " << tp << " for prosecution and value " << td << " for defence:" << endl;
        for(int i = 1; i <= m; ++i)
            cout << cand[i] << " ";
        cout << endl;
        cout << endl;
    }
}

$4 混合背包

混合背包问题

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

物品一共有三类：

  • 第一类物品只能用1次（01背包）；
  • 第二类物品可以用无限次（完全背包）；
  • 第三类物品最多只能用 si 次（多重背包）；

每种体积是 vi，价值是 wi。

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

算法：混合背包

对每个阶段面对的物品things[i]，先判断种类，转移时按照那一类的转移方式进行转移。

种类分为 01 背包和完全背包两种，多重背包的部分按照二进制划分分成 logS[i] 变成 01 背包

代码 (C++)

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
#include <vector>
#include <iostream>

using namespace std;

struct Thing
{
    int kind;
    int v, w;
};


int main()
{
    int N;
    int V;
    cin >> N >> V;
    vector<int> v(N, 0);
    vector<int> w(N, 0);
    vector<int> s(N, 0);
    for(int i = 0; i < N; ++i)
        cin >> v[i] >> w[i] >> s[i];
    
    vector<Thing> things;

    vector<int> dp(V + 1, 0);

    for(int i = 0; i < N; ++i)
    {
        int ss = s[i], vv = v[i], ww = w[i];
        if(ss < 0) things.push_back({-1, vv, ww});
        else if(ss == 0) things.push_back({0, vv, ww});
        else
        {
            for(int k = 1; k <= ss; k *= 2)
            {
                ss -= k;
                things.push_back({-1, vv * k, ww * k});
            }
            if(ss > 0)
                things.push_back({-1, vv * ss, ww * ss});
        }
    }

    for(auto thing: things)
    {
        if(thing.kind < 0)
        {
            for(int j = V; j >= thing.v; --j)
                dp[j] = max(dp[j], dp[j - thing.v] + thing.w);
        }
        else
        {
            for(int j = thing.v; j <= V; ++j)
                dp[j] = max(dp[j], dp[j - thing.v] + thing.w);
        }
    }

    cout << dp[V] << endl;
    return 0;
}
Share