文章

01背包、有依赖的背包

01背包问题通过选择物品最大化价值，每个物品只能选一次。有依赖的背包问题则在选择物品时考虑物品间的依赖关系，增加了约束和复杂性。

发表于 更新于
作者 Sylvan
23 分钟阅读
01背包、有依赖的背包

01背包、有依赖的背包

P1048 [NOIP2005 普及组] 采药

01背包(模版)

给定一个正数 t，表示背包的容量 有 m 个货物，每个货物可以选择一次 每个货物有自己的体积 costs[i] 和价值 values[i] 返回在不超过总容量的情况下，怎么挑选货物能达到价值最大 返回最大的价值

  • 二维 dp 数组
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

#include <iostream>
#include <vector>

using namespace std;

int bag(vector<int> &cost, vector<int> &value, int t, int n) {
    // dp[i][j] 表示在前 i 种物品中选择，总代价不超过 j 的情况下，能获得的最大价值
    vector<vector<int>> dp(n + 1, vector<int>(t + 1));
    // 第一行为 0
    fill(dp[0].begin(), dp[0].end(), 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= t; ++j) {
            // 不选 i 号物品，则最大价值和在前 i - 1 个物品中选，总代价不超过 j 的情况下能获得的最大价值一样
            dp[i][j] = dp[i - 1][j];
            // 选 i 号物品，价值就是 i 号物品的价值加上在前 i - 1 个物品中选，总代价不超过 j - cost[i] 的情况下能获得的最大价值
            if (j - cost[i] >= 0)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - cost[i]] + value[i]);
        }
    }
    // 返回在 n 种物品中选择，总代价不超过 t 的情况下，能获得的最大价值
    return dp[n][t];
}

int main() {
    // t 为背包容量，n 为物品种数
    int t, n;
    cin >> t >> n;
    // 物品从 1 编号
    vector<int> cost(n + 1);
    vector<int> value(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> cost[i] >> value[i];
    cout << bag(cost, value, t, n);
}
  • 空间压缩
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 <iostream>
#include <vector>

using namespace std;

int bag(vector<int> &cost, vector<int> &value, int t, int n) {
    // 原矩阵的每一行，逐行往下，第一行为 0
    vector<int> dp(t + 1, 0);
    for (int i = 1; i <= n; ++i) 
        // 如果从左往右的话就需要两个一维数组了，因为从左往右的过程中会覆盖掉 dp[j - cost[i]]
        // 从右往左可以避免这个问题
        // dp[j] 继承自上一行的 dp[j] 不变，表示不选 i 号物品
        // 或者选 i 号物品，价值就是 i 号物品的价值加上在前 i - 1 个物品中选，总代价不超过 j - cost[i] 的情况下能获得的最大价值
        // dp[j - cost[i]] 也来自上一行
        for (int j = t; j - cost[i] >= 0; j--)
            dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);
    // 返回在 n 种物品中选择，总代价不超过 t 的情况下，能获得的最大价值
    return dp[t];
}

int main() {
    // t 为背包容量，n 为物品种数
    int t, n;
    cin >> t >> n;
    // 物品从 1 编号
    vector<int> cost(n + 1);
    vector<int> value(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> cost[i] >> value[i];
    cout << bag(cost, value, t, n);
}

bytedance-006. 夏季特惠

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

#include <iostream>
#include <vector>

using namespace std;

#define ll  long long

// 返回在 n 种物品中选择，总代价不超过 x 的情况下，能获得的最大价值
ll bag(vector<int> &cost, vector<ll> &value, int x) {
    int n = cost.size() - 1;
    vector<ll> dp(x + 1, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = x; j - cost[i] >= 0; j--)
            dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);
    return dp[x];
}

int main() {
    // x 为预算
    int n, x;
    cin >> n >> x;
    // 待考虑的商品，下标从 1 开始
    vector<int> cost(1);
    // 快乐值
    vector<ll> value(1);
    // 获得的快乐值
    ll res = 0;
    int before, now;
    ll happy;
    for (int i = 1; i <= n; ++i) {
        cin >> before >> now >> happy;
        int val = before - now - now;
        if (val > 0) {
            // 优惠的钱比购买价格还高，一定购买，会使心里预算增加
            x += val;
            res += happy;
        } else {
            cost.emplace_back(-val);
            value.emplace_back(happy);
        }
    }
    cout << res + bag(cost, value, x);
}

494. 目标和

  • 暴力递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <vector>

using namespace std;

class Solution {
public:
    int res;

    // 暴力递归
    void recursive(vector<int> &nums, int target, int curIndex, int sum) {
        if (curIndex == nums.size()) {
            if (sum == target) res++;
            return;
        }
        recursive(nums, target, curIndex + 1, sum + nums[curIndex]);
        recursive(nums, target, curIndex + 1, sum - nums[curIndex]);
    }

    int findTargetSumWays(vector<int> &nums, int target) {
        res = 0;
        recursive(nums, target, 0, 0);
        return res;
    }
};
  • 带返回值的暴力递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <vector>

using namespace std;

class Solution {
public:
    int recursive(vector<int> &nums, int target, int curIndex, int sum) {
        if (curIndex == nums.size())
            return sum == target ? 1 : 0;
        return recursive(nums, target, curIndex + 1, sum + nums[curIndex])
               + recursive(nums, target, curIndex + 1, sum - nums[curIndex]);
    }

    int findTargetSumWays(vector<int> &nums, int target) {
        return recursive(nums, target, 0, 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

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    unordered_map<int, unordered_map<int, int>> dp;

    // 记忆化搜索版
    // 本来使用 dp[curIndex][sum] 记录，但是 sum 可能是负数
    // 所以用二级哈希表模拟
    int recursive(vector<int> &nums, int target, int curIndex, int sum) {
        if (curIndex == nums.size())
            return sum == target ? 1 : 0;
        if (dp.find(curIndex) != dp.end() && dp[curIndex].find(sum) != dp[curIndex].end())
            return dp[curIndex][sum];
        int res = recursive(nums, target, curIndex + 1, sum + nums[curIndex])
                  + recursive(nums, target, curIndex + 1, sum - nums[curIndex]);
        dp[curIndex].emplace(sum, res);
        return res;
    }

    int findTargetSumWays(vector<int> &nums, int target) {
        return recursive(nums, target, 0, 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

#include <vector>

using namespace std;

class Solution {
public:
    // todo
    int findTargetSumWays(vector<int> &nums, int target) {
        int s = 0;
        for (const auto &item: nums)
            s += item;
        // 不在范围内，凑不出来
        if (target < -s || target > s) return 0;
        int n = nums.size();
        int m = 2 * s + 1;
        // 原本的 dp[i][j] 含义:
        // nums[0, i-1] 范围上，已经形成的累加和是 sum
        // 为了避免 sum 为负数的情况，dp[i][j] 平移为 dp[i][j + s]
        vector<vector<int>> dp(n + 1, vector<int>(m));
        dp[n][target + s] = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = -s; j <= s; j++) {
                if (j + nums[i] + s < m)
                    dp[i][j + s] = dp[i + 1][j + nums[i] + s];
                if (j - nums[i] + s >= 0)
                    dp[i][j + s] += dp[i + 1][j - nums[i] + s];
            }
        }
        return dp[0][s];
    }
};
  • 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

#include <vector>

using namespace std;

class Solution {
public:
    // 求非负数组 nums 有多少个子序列累加和是 t
    // 01 背包问题(子集累加和严格是 t) + 空间压缩
    // dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
    int subsets(vector<int> &nums, int t) {
        if (t < 0) return 0;
        vector<int> dp(t + 1, 0);
        dp[0] = 1;
        for (int num: nums)
            for (int j = t; j - num >= 0; j--)
                dp[j] += dp[j - num];
        return dp[t];
    }

    // 比如说给定一个数组, nums = [1, 2, 3, 4, 5] 并且 target = 3
    // 其中一个方案是 : +1 -2 +3 -4 +5 = 3
    // 该方案中取了正的集合为A = {1，3，5}
    // 该方案中取了负的集合为B = {2，4}
    // 所以任何一种方案，都一定有 sum(A) - sum(B) = target
    // 现在我们来处理一下这个等式，把左右两边都加上sum(A) + sum(B)，那么就会变成如下：
    // sum(A) - sum(B) + sum(A) + sum(B) = target + sum(A) + sum(B)
    // 2 * sum(A) = target + 数组所有数的累加和
    // sum(A) = (target + 数组所有数的累加和) / 2
    // 也就是说，任何一个集合，只要累加和是(target + 数组所有数的累加和) / 2
    // 那么就一定对应一种target的方式
    // 比如非负数组nums，target = 1, nums所有数累加和是11
    // 求有多少方法组成1，其实就是求，有多少种子集累加和达到6的方法，(1+11)/2=6
    // 因为，子集累加和6 - 另一半的子集累加和5 = 1（target)
    // 所以有多少个累加和为6的不同集合，就代表有多少个target==1的表达式数量
    // 至此已经转化为01背包问题了
    int findTargetSumWays(vector<int> &nums, int target) {
        int sum = 0;
        for (int num: nums) sum += num;
        // 范围外凑不出 target，奇偶性不一致也凑不出
        if (target < -sum || sum < target || ((target & 1) ^ (sum & 1)) == 1) return 0;
        return subsets(nums, (target + sum) >> 1);
    }
};

1049. 最后一块石头的重量 II

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>

using namespace std;

class Solution {
public:
    // 非负数组 nums 中，子序列累加和不超过 t，但是最接近 t 的累加和是多少
    // 01 背包问题(子集累加和尽量接近 t) + 空间压缩
    int getNear(vector<int> &nums, int t) {
        vector<int> dp(t + 1);
        for (int num: nums)
            for (int j = t; j - num >= 0; j--)
                // dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
                dp[j] = max(dp[j], dp[j - num] + num);
        return dp[t];
    }

    int lastStoneWeightII(vector<int> &stones) {
        int sum = 0;
        for (int num: stones)
            sum += num;
        // nums 中随意选择数字，累加和一定要 <= sum / 2，又尽量接近
        int near = getNear(stones, sum / 2);
        return sum - near - near;
    }
};

P1064 [NOIP2006 提高组] 金明的预算方案

有依赖的背包(模版)

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;

int main() {
    int n, m;
    cin >> n >> m;
    // 代价
    vector<int> cost(m + 1);
    // 收益
    vector<int> value(m + 1);
    // 是否是主商品
    vector<bool> king(m + 1);
    // 主商品的附属商品
    vector<vector<int>> follows(m + 1);

    // 编号从 1 开始
    for (int i = 1, v, p, q; i <= m; ++i) {
        cin >> v >> p >> q;
        cost[i] = v;
        value[i] = v * p;
        king[i] = q == 0;
        if (q != 0) follows[q].emplace_back(i);
    }

    // dp[i][j] 表示前 i 个商品中，只关心主商品，并且进行展开，花费不超过 j 的情况下，获得的最大收益
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    // 上次展开的主商品编号
    int pre = 0;
    for (int i = 1, fan1, fan2; i <= m; ++i) {
        // 跳过附属商品
        if (!king[i]) continue;
        for (int j = 0; j <= n; ++j) {
            // 可能性1: 不考虑当前主商品
            dp[i][j] = dp[pre][j];
            // 可能性2: 考虑当前主商品，只要主
            if (j - cost[i] >= 0)
                dp[i][j] = max(dp[i][j],
                               dp[pre][j - cost[i]] + value[i]);
            // fan1: 如果有附 1 商品，编号给 fan1，如果没有，fan1 == -1
            // fan2: 如果有附 2 商品，编号给 fan2，如果没有，fan2 == -1
            fan1 = follows[i].size() >= 1 ? follows[i][0] : -1;
            fan2 = follows[i].size() >= 2 ? follows[i][1] : -1;
            // 可能性3: 主 + 附1
            if (fan1 != -1 && j - cost[i] - cost[fan1] >= 0)
                dp[i][j] = max(dp[i][j],
                               dp[pre][j - cost[i] - cost[fan1]] + value[i] + value[fan1]);
            // 可能性4: 主 + 附2
            if (fan2 != -1 && j - cost[i] - cost[fan2] >= 0)
                dp[i][j] = max(dp[i][j],
                               dp[pre][j - cost[i] - cost[fan2]] + value[i] + value[fan2]);
            // 可能性5: 主 + 附1 + 附2
            if (fan1 != -1 && fan2 != -1 && j - cost[i] - cost[fan1] - cost[fan2] >= 0)
                dp[i][j] = max(dp[i][j],
                               dp[pre][j - cost[i] - cost[fan1] - cost[fan2]] + value[i] + value[fan1] + value[fan2]);
        }
        pre = i;
    }
    cout << dp[pre][n];
}
  • 空间压缩
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

#include <vector>
#include <iostream>

using namespace std;

int main() {
    // m 种商品，总金额 n
    int n, m;
    cin >> n >> m;
    // 代价
    vector<int> cost(m + 1);
    // 收益
    vector<int> value(m + 1);
    // 是否是主商品
    vector<bool> king(m + 1);
    // 主商品的附属商品
    vector<vector<int>> follows(m + 1);

    // 编号从 1 开始
    for (int i = 1, v, p, q; i <= m; ++i) {
        cin >> v >> p >> q;
        cost[i] = v;
        value[i] = v * p;
        king[i] = q == 0;
        if (q != 0) follows[q].emplace_back(i);
    }

    // dp[i][j] 表示前 i 个商品中，只关心主商品，并且进行展开，花费不超过 j 的情况下，获得的最大收益
    // 首行为 0
    vector<int> dp(n + 1, 0);
    for (int i = 1, fan1, fan2; i <= m; ++i) {
        // 跳过附属商品
        if (!king[i]) continue;
        // 从右往左
        for (int j = n; j - cost[i] >= 0; j--) {
            // 可能性1: 不考虑当前主商品
            // 可能性2: 考虑当前主商品，只要主
            dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);
            fan1 = follows[i].size() >= 1 ? follows[i][0] : -1;
            fan2 = follows[i].size() >= 2 ? follows[i][1] : -1;
            // 可能性3: 主 + 附1
            if (fan1 != -1 && j - cost[i] - cost[fan1] >= 0)
                dp[j] = max(dp[j], dp[j - cost[i] - cost[fan1]] + value[i] + value[fan1]);
            // 可能性4: 主 + 附2
            if (fan2 != -1 && j - cost[i] - cost[fan2] >= 0)
                dp[j] = max(dp[j], dp[j - cost[i] - cost[fan2]] + value[i] + value[fan2]);
            // 可能性5: 主 + 附1 + 附2
            if (fan1 != -1 && fan2 != -1 && j - cost[i] - cost[fan1] - cost[fan2] >= 0)
                dp[j] = max(dp[j], dp[j - cost[i] - cost[fan1] - cost[fan2]] + value[i] + value[fan1] + value[fan2]);
        }
    }
    cout << dp[n];
}

非负数组前k个最小的子序列累加和

非负数组前k个最小的子序列累加和 给定一个数组 nums，含有 n 个数字，都是非负数 给定一个正数 k，返回所有子序列中累加和最小的前 k 个累加和 子序列是包含空集的 1 <= n <= 10^5 1 <= nums[i] <= 10^6 1 <= k <= 10^5 注意这个数据量，用 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
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <random>

using namespace std;

// 非负数组前k个最小的子序列累加和
// 给定一个数组nums，含有n个数字，都是非负数
// 给定一个正数k，返回所有子序列中累加和最小的前k个累加和
// 子序列是包含空集的
// 1 <= n <= 10^5
// 1 <= nums[i] <= 10^6
// 1 <= k <= 10^5
class Solution {
public:
    // 暴力方法
    vector<int> topKSum1(vector<int> &nums, int k) {
        // 所有子序列的和
        vector<int> allSubsequences;
        recursive(nums, 0, 0, allSubsequences);
        sort(allSubsequences.begin(), allSubsequences.end());
        vector<int> res(k);
        // 取前 k 个
        for (int i = 0; i < k; i++)
            res[i] = allSubsequences[i];
        return res;
    }

    // 得到所有子序列的和
    void recursive(vector<int> &nums, int curIndex, int sum, vector<int> &res) {
        if (curIndex == nums.size()) {
            res.push_back(sum);
            return;
        }
        // 不要当前
        recursive(nums, curIndex + 1, sum, res);
        // 要当前
        recursive(nums, curIndex + 1, sum + nums[curIndex], res);
    }

    // 01 背包来实现，时间复杂度太差，因为 n 很大，数值也很大，那么可能的累加和就更大
    vector<int> topKSum2(vector<int> &nums, int k) {
        int sum = 0;
        for (int num: nums) sum += num;
        vector<int> dp(sum + 1, 0);
        dp[0] = 1;
        for (int num: nums)
            // 从右往左
            for (int j = sum; j - num >= 0; j--)
                dp[j] += dp[j - num];
        vector<int> res(k);
        int index = 0;
        for (int j = 0; j <= sum && index < k; j++)
            for (int i = 0; i < dp[j] && index < k; i++)
                res[index++] = j;
        return res;
    }

    struct cmp {
        bool operator()(pair<int, int> &p1, pair<int, int> &p2) {
            return p1.second > p2.second;
        }
    };

    // 正式方法
    // 用堆来做是最优解，时间复杂度 O(n * log n) + O(k * log k)
    vector<int> topKSum3(vector<int> &nums, int k) {
        sort(nums.begin(), nums.end());
        // <子序列的最右下标，子序列的累加和>，根据累加和递增
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> heap;
        heap.push({0, nums[0]});

        vector<int> res(k);
        res[0] = 0;
        for (int i = 1; i < k; i++) {
            pair<int, int> cur = heap.top();
            heap.pop();
            int right = cur.first;
            int sum = cur.second;
            // 收集弹出的最小累加和
            res[i] = sum;
            if (right + 1 < nums.size()) {
                // 去掉末尾，加上下个数
                heap.push({right + 1, sum - nums[right] + nums[right + 1]});
                // 不去掉末尾，加上下个数
                heap.push({right + 1, sum + nums[right + 1]});
            }
        }
        return res;
    }

    // 为了测试
    vector<int> randomArray(int len, int value) {
        vector<int> ans(len);
        random_device rd;
        mt19937 gen(rd());
        uniform_int_distribution<> dis(0, value);
        for (int i = 0; i < len; i++)
            ans[i] = dis(gen);
        return ans;
    }

    // 为了测试
    bool equals(const vector<int> &ans1, const vector<int> &ans2) {
        if (ans1.size() != ans2.size()) return false;
        for (int i = 0; i < ans1.size(); i++)
            if (ans1[i] != ans2[i])
                return false;
        return true;
    }
};

int main() {
    Solution solution;
    int n = 15;
    int v = 40;
    int testTime = 5000;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTime; i++) {
        int len = rand() % n + 1;
        vector<int> nums = solution.randomArray(len, v);
        int k = rand() % ((1 << len) - 1) + 1;
        vector<int> ans1 = solution.topKSum1(nums, k);
        vector<int> ans2 = solution.topKSum2(nums, k);
        vector<int> ans3 = solution.topKSum3(nums, k);
        if (!solution.equals(ans1, ans2) || !solution.equals(ans1, ans3))
            cout << "出错了！" << endl;
    }
    cout << "测试结束" << endl;
}
algorithm, problems
Algorithm Knapsack problem
本文由作者按照 CC BY 4.0 进行授权