算法设计与分析 SCAU19185 01背包问题 C++

19185 01背包问题

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

一个旅行者有一个最多能装 M公斤的背包，现在有 n件物品，它们的重量分别是W1，W2，…,。
它们的价值分别为C1,C2,…,，求旅行者在不超过背包重量M的情况下，能获得最大总价值。
PS：01背包问题也能用于个人的时间管理，如何分配时间在不同的任务上，才能最大化提升个人价值。

输入格式

第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；

第2…N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。

输出格式

一个数，表示最大总价值。

输入样例

10 4
2 1
3 3
4 5
7 9

输出样例

12

解题思路

先定义题目所需的常量

const int MAXN = 201;
int v[MAXN]; // 体积
int w[MAXN]; // 价值
int dp[MAXN][MAXN]; // dp[i][j], j体积下前i个物品的最大价值
1
2
3
4

1. dp 方程定义

• dp[i][j] 表示从前 i 个物品中选，选出的总体积小于 j 的最优解。
• 可以从 f[0][0] = 0 开始遍历，有 N 个物品，需要 N 次遍历
• 而在每件物品时都有 M 个容纳体积可支配，再进行 M 次遍历。
• 因此 dp[i][j] 不断由之前的状态更新而来。

2. 状态转移方程

我们将所有状态分为两类，第一类不含第 i 件物品，第二类含第 i 件物品，取决于第 i 件物品体积是否大于当前背包所能容纳的大小。例如：当前背包最大容纳量只有5，如果物品体积为7，那么很明显装不进来；注意第二类只有在 v[i] <= j 时才存在。

• 第一类不含 i，那就是在前 1 到 i - 1 件物品中选容量不超过 j 的最优选，最优选为 dp[i - 1][j]。
• 第二类为含 i 的，因为直接求解不好求，我们可以先将 i 减去，最后在加上 i。也就是在前 1 到 i - 1 中选物品体积不超过 j - v[i] (j 为背包当前最大容纳量，v[i] 为当前要添加的物品体积)；此时价值为 dp[i - 1][j - v[i]] + w[i]; 例如：当前容纳体积为 j = 5，如果要加入体积为3的物品，那么肯定是在计算体积为2的价值基础上，再加上新的物品价值。
• 最后我们要做的时求第一类和第二类的 max；

3. 算法解题思路

1. 初始化0件物品时的各个体积的价值，方便计算
2. 双层 for 循环，外层是第 i 件物品，内层是背包所能容纳的最大体积 j
3. 判断，若此时要加入的第 i 件物品体积如果直接大于背包当前所能容纳的体积 j，那么加入不了，直接取上一个物品相同容纳体积的数据
4. 若能装，需进行决策是否选择第 i 个物品，第二个比较对象为：在减去要新加的物品体积 v[i] 基础上，加上新价值看看如何，即 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);

更多注释可查看下方的完整代码中，有助于理解

代码如下

#include 

using namespace std;

const int MAXN = 201;
int v[MAXN]; // 体积
int w[MAXN]; // 价值
int dp[MAXN][MAXN]; // dp[i][j], j体积下前i个物品的最大价值
/*
10 4
2 1
3 3
4 5
7 9
*/
int main()
{
    int i, j, M, N; // M为背包容量，N为物品数量
    cin >> M >> N;

    for(i = 1; i <= N; i++) {
        cin >> v[i] >> w[i];
    }

    // 初始化0件物品时的各个体积的价值，方便计算
    for(i = 0; i <= M; i++) {
        dp[0][i] = 0;
    }

    for(i = 1; i <= N; i++) {
        for(j = 1; j <= M; j++) {
            // 此时要加入的第i件物品体积如果直接大于 背包当前所能容纳的体积j，那么加入不了，直接取上一个物品相同容纳体积的数据
            if(v[i] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                // 能装，需进行决策是否选择第i个物品，第二个比较对象为：在减去要新加的物品体积v[i] 基础上，加上新价值看看如何
                // 例如：当前容纳体积为 j=5，如果要加入体积为3的物品，那么肯定是在计算体积为2的价值基础上，再加上新的物品价值
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
            }
            // cout << "i=" << i << " j=" << j << " " << dp[i][j] << endl;
        }
    }


    cout << dp[N][M] << endl;
    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

最后

对我感兴趣的小伙伴可查看以下链接

• 我的掘金主页：https://juejin.cn/user/1302297507801358
• 博客主页：http://blog.zhangjiancong.top/
• 公众号：Smooth前端成长记录