计算机科学基础leetcode刷题动态规划
Source
Edit
History

背包问题01背包

二维背包

一维背包

注意点：

  1. 初始化容易搞错，从weight[0]开始初始化，将后面大于weight[0]的初始化为weight[0]

代码

下面是代码时间，卡码网的01背包问题。

46. 携带研究材料（第六期模拟笔试） (kamacoder.com)

我们可以明显看出一维背包比二维背包少了很多代码。

二维背包

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
#include<iostream>
#include<vector>
using namespace std;
void debug(vector<vector<int>> dp) {
    for(int i = 0; i < dp.size(); i++) {
        for(int j = 0; j < dp[0].size(); j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
}
int max_value(vector<int> weights,vector<int> values,int bag_size) {
    //dp数组的含义 dp[i][j] 
    vector<vector<int>> dp(weights.size(),vector<int>(bag_size + 1,0));
    //初始化
    for (int j = 0; j <= bag_size ; j++) {
        if(j >= weights[0]) {
            dp[0][j] = values[0];
        }
    }
    // debug(dp);
    //开始dp推导
    for(int i = 1; i < dp.size(); i++) {
        for(int j = 1; j < dp[0].size(); j++) {
            if(j  >= weights[i]) {//是否装得下这个物品
                //放物品i价值大  还是  不放物品i价值大
                dp[i][j] = max(dp[i-1][j],dp[i-1][j- weights[i]] + values[i]);
            } else {
                 dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[dp.size() - 1][bag_size];
}
int main(){
    int m,n;
    vector<int> weights;
    vector<int> values;
    cin >> m >> n;
    for(int i = 0; i < m; i++) {
        int temp;
        cin >> temp;
        weights.push_back(temp);
    }
    for(int i = 0; i < m; i++) {
        int temp;
        cin >> temp;
        values.push_back(temp);
    }
    // for(int i = 0; i < m; i++) {
    //     cout << weights[i] << "--" << values[i] << endl;
    // }
    int maxv = max_value(weights,values,n);
    cout << maxv << endl;
}

一维背包

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
#include<iostream>
#include<vector>
using namespace std;
void debug(vector<int> dp) {
    for(int i = 0; i < dp.size(); i++) {
        cout << dp[i] << " " ;
    }
    cout << endl;
}
int max_value(vector<int> weights,vector<int> values,int bag_size) {
    //dp数组的含义 容量为j的背包的最大价值为 dp[j]  
    vector<int> dp(bag_size + 1,0);
    //开始dp推导
    for(int i = 0; i < weights.size(); i++) {
        for(int j = bag_size; j >= 0; j--) {
            if(j  >= weights[i]) {//是否装得下这个物品
                //放物品i价值大  还是  不放物品i价值大
                dp[j] = max(dp[j],dp[j- weights[i]] + values[i]);
            }
        }
        // debug(dp);
    }
    return dp[bag_size];
}
int main(){
    int m,n;
    vector<int> weights;
    vector<int> values;
    cin >> m >> n;
    for(int i = 0; i < m; i++) {
        int temp;
        cin >> temp;
        weights.push_back(temp);
    }
    for(int i = 0; i < m; i++) {
        int temp;
        cin >> temp;
        values.push_back(temp);
    }
    // for(int i = 0; i < m; i++) {
    //     cout << weights[i] << "--" << values[i] << endl;
    // }
    int maxv = max_value(weights,values,n);
    cout << maxv << endl;
}