0-1 背包

给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

明确状态和选择

  1. 明确状态：背包的容量和可选择的物品
  2. 明确选择：对于一个物品，可以选择装进背包，或者选择不装进背包

定义 dp 数组

状态有两个，所以需要二维 dp 数组 dp[i][w]

dp[i][w] 含义：对于前 i 个物品，背包容量为 w 时能够获得的最大价值

我们需要的答案就是 dp[N][W]

当物品为 0 或者背包容量为 0 时获得的价值为 0 ，所以 base case 就是 dp[0][…] = dp[…][0] = 0

寻找状态转移方程

如何计算 dp[i][w] 呢？对于第 i 个物品：

  1. 如果背包的剩余容量以及装不下 i 了，即 w - w[i] < 0 , 此时总的价值等于 dp[i-1][w]
  2. 剩余容量能够装下 i
    • 如果不把它放进背包，那总的价值等于 dp[i-1][w]
    • 如果将它放进背包，那总的价值等于 value[i] + dp[i-1][w - w[i]] ，即当前物品价值加上前 i - 1 个物品，背包容量为 w - value[i] 时获得的最大价值。
    • dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - value[i]])

套用框架写出代码

1
2
3
4

for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 择优(选择1，选择2...)


1
2
3
4
5

4 5
1 2
2 4
3 4
4 5

 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

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

// capacity: 背包容量
// n: 种类数
// weight[i-1]: 第 i 种物品的重量，i 从 0 计算
// value[i-1]: 第 i 种物品的价值，i 从 0 计算
int knapsack_0_1(int capacity, int n, const vector<int>& weight, const vector<int>& value) {
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (j - weight[i - 1] < 0) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - weight[i - 1]]);
            }
        }
    }
    return dp[n][capacity];
}

int main(int argc, char* argv[]) {
    int capacity, n;
    cin >> n >> capacity;

    vector<int> weight(n, 0);
    vector<int> value(n, 0);

    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }

    int result = knapsack_0_1(capacity, n, weight, value);

    cout << result << endl;

    return 0;
}

1

8

优化 dp 数组空间

可以看到 dp[i][j] 计算时只依赖 dp[i-1][...j] ，即只用到了上一行，所以可以用一维数组存储上一行的信息。

由于 dp[i][j] 中的 j 依赖于 [...j] 前面的数据，所以我们要从后往前计算 j ，避免新的数据覆盖需要的数据

 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

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

// capacity: 背包容量
// n: 种类数
// weight[i-1]: 第 i 种物品的重量，i 从 0 计算
// value[i-1]: 第 i 种物品的价值，i 从 0 计算
int knapsack_0_1(int capacity, int n, const vector<int>& weight, const vector<int>& value) {
    vector<int> dp(capacity + 1);

    for (int i = 1; i <= n; i++) {
        for (int j = capacity; j >= weight[i - 1]; j--) {
            dp[j] = max(dp[j], value[i - 1] + dp[j - weight[i - 1]]);
        }
    }
    return dp[capacity];
}

int main(int argc, char* argv[]) {
    int capacity, n;
    cin >> n >> capacity;

    vector<int> weight(n, 0);
    vector<int> value(n, 0);

    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }

    int result = knapsack_0_1(capacity, n, weight, value);

    cout << result << endl;

    return 0;
}

1

8

例题链接

https://www.acwing.com/problem/content/2/

完全背包

完全背包和 0-1 背包类似，不同的点是每个物品的数量是无限的，可以选无限次，而不是一次。

明确状态和选择

  1. 明确状态：背包的容量和可选择的物品
  2. 明确选择：对于第 i 个物品，可以选择装 k 个进背包，或者选择不装进背包

定义 dp 数组

状态有两个，所以需要二维 dp 数组 dp[i][w]

dp[i][w] 含义：对于前 i 个物品（可以重复选择），背包容量为 w 时能够获得的最大价值

我们需要的答案就是 dp[N][W]

当物品为 0 或者背包容量为 0 时获得的价值为 0 ，所以 base case 就是 dp[0][…] = dp[…][0] = 0

寻找状态转移方程

如何计算 dp[i][w] 呢？对于第 i 个物品：

  1. 如果背包容量一个 i 都放不下，=dp[i][w] = dp[i-1][w]=
  2. 如果背包容量至少可以放一个 i ，虽然 i 的个数是无限的，但是实际能够放 i 的个数为 w/w[i] ：
    • 第 i 个物品的可选择的个数就为 [0..w/w[i]]
    • dp[i][w] = max(dp[i-1][w-0 * w[i]], ..., value[i]*w/w[i] +dp[i-1][w-w/w[i]*w[i]])

根据框架写出代码

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

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

1
2
3
4
5

4 5
1 2
2 4
3 4
4 5

 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

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

// capacity: 背包容量
// n: 种类数
// weight[i-1]: 第 i 种物品的重量，i 从 0 计算
// value[i-1]: 第 i 种物品的价值，i 从 0 计算
int knapsack_inf(int capacity, int n, const vector<int>& weight, const vector<int>& value) {

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (j - weight[i - 1] < 0) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j];  // 不选择
                for (int k = 1; k * weight[i - 1] <= j; k++) { // 在 1.. k 中求最优
                    dp[i][j] = max(dp[i][j], value[i - 1] * k + dp[i - 1][j - k * weight[i - 1]]);
                }
            }
        }
    }
    return dp[n][capacity];
}

int main(int argc, char* argv[]) {
    int capacity, n;
    cin >> n >> capacity;

    vector<int> weight(n, 0);
    vector<int> value(n, 0);

    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }

    int result = knapsack_inf(capacity, n, weight, value);

    cout << result << endl;

    return 0;
}

1

10

优化时间复杂度

1
2
3

for (int k = 1; k * weight[i - 1] <= j; k++) {  // 在 1.. k 中求最优
    dp[i][j] = max(dp[i][j], value[i - 1] * k + dp[i - 1][j - k * weight[i - 1]]);
}

上面这段代码中存在重复计算，比如当 k 为 0， 1， 2 时 ，

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i)] + v[i], dp[i-1][j-w[i]*2] + v[i]*2)

当 j = j-w[i] 时

dp[i][j-w[i]] = max(dp[i-1][j-w[i]], dp[i-1][j-w[i]*2] + v[i], dp[i-1][j-w[i]*3] + v[i]*2)

所以当 j 从前往后时， dp[i][j-w[i]] 已经由 dp[i-1][j-w[i]*2] 更新过，所以优化后的状态转移为：

dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-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
32
33
34
35
36
37
38
39
40
41
42
43

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

// capacity: 背包容量
// n: 种类数
// weight[i-1]: 第 i 种物品的重量，i 从 0 计算
// value[i-1]: 第 i 种物品的价值，i 从 0 计算
int knapsack_inf(int capacity, int n, const vector<int>& weight, const vector<int>& value) {

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (j - weight[i - 1] < 0) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);
            }
        }
    }
    return dp[n][capacity];
}

int main(int argc, char* argv[]) {
    int capacity, n;
    cin >> n >> capacity;

    vector<int> weight(n, 0);
    vector<int> value(n, 0);

    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }

    int result = knapsack_inf(capacity, n, weight, value);

    cout << result << endl;

    return 0;
}

1

10

优化空间复杂度

类似的， dp[i][j] 的计算只依赖于 dp[i-1] 的数据，所以可以用一维数组滚动计算。

注意， dp[i][j] 的计算依赖于前面计算的 dp[i][j-w[i]] ，所以需要 j 需要从前往后计算

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

using namespace std;

// capacity: 背包容量
// n: 种类数
// weight[i-1]: 第 i 种物品的重量，i 从 0 计算
// value[i-1]: 第 i 种物品的价值，i 从 0 计算
int knapsack_inf(int capacity, int n, const vector<int>& weight, const vector<int>& value) {

    vector<int> dp(capacity + 1);

    for (int i = 1; i <= n; i++) {
        for (int j = weight[i - 1]; j <= capacity; j++) {
            dp[j] = max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
        }
    }
    return dp[capacity];
}

int main(int argc, char* argv[]) {
    int capacity, n;
    cin >> n >> capacity;

    vector<int> weight(n, 0);
    vector<int> value(n, 0);

    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }

    int result = knapsack_inf(capacity, n, weight, value);

    cout << result << endl;

    return 0;
}

1

10

例题

https://www.acwing.com/problem/content/3/

多重背包问题

和完全背包类似，但是第 i 种物品的个数限制为 nums[i] 个 ，而完全背包的物品个数不限。

所以我们可以直接套用完全背包的解决方法，需要注意的是每种物品最多只有 nums[i] 个

多重背包无法像完全背包一样进行时间优化，消除 k ，因为每个物品不是无限，不能放任意次数。

下面是空间优化后的版本

1
2
3
4
5

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

 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

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

// capacity: 背包容量
// n: 种类数
// weight[i-1]: 第 i 种物品的重量，i 从 0 计算
// value[i-1]: 第 i 种物品的价值，i 从 0 计算
// nums[i-1]: 第 i 种物品的数量
int knapsack_nums(int capacity, int n, const vector<int>& weight, const vector<int>& value,
                  const vector<int>& nums) {

    vector<int> dp(capacity + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = capacity; j >= weight[i - 1]; j--) {
            for (int k = 1; k <= nums[i - 1] && (j - k * weight[i - 1]) >= 0; k++) {
                dp[j] = max(dp[j], value[i - 1] * k + dp[j - k * weight[i - 1]]);
            }
        }
    }
    return dp[capacity];
}
int main(int argc, char* argv[]) {
    int capacity, n;
    cin >> n >> capacity;

    vector<int> weight(n, 0);
    vector<int> value(n, 0);
    vector<int> nums(n, 0);

    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i] >> nums[i];
    }

    int result = knapsack_nums(capacity, n, weight, value, nums);

    cout << result << endl;

    return 0;
}

1

10

二进制优化