01背包

# 思路

# 二维数组

笔记

base case: 都初始化为 0

提示

遍历顺序：可以先遍历物品再遍历背包，也可以先遍历背包再遍历物品

# 滚动数组优化

# 题目

# HDU 2602

https://acm.hdu.edu.cn/showproblem.php?pid=2602

先输入有多少个物品，然后是总容量

前一行是物品价值，后一行是物品容量

# 二维数组

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

using namespace std;

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n, m;
        scanf("%d %d", &n, &m);

        vector<int> w(n, 0), v(n, 0);
        for(int i = 0; i < n; i++) scanf("%d", &v[i]);
        for(int i = 0; i < n; i++) scanf("%d", &w[i]);


        vector<vector<int> > dp(n+1, vector<int>(m+1, 0));
        for(int i = 0; i < n; i++){
            for(int j = 0; j <= m; j++){
                if(w[i] > j) dp[i+1][j] = dp[i][j];
                else{
                    dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
                }
            }
        }
        printf("%d\n", dp[n][m]);
    }

    return 0;
}
// 01 背包 2602
// 完全背包 1114

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

using namespace std;

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n, m;
        scanf("%d %d", &n, &m);

        vector<int> w(n, 0), v(n, 0);
        for(int i = 0; i < n; i++) scanf("%d", &v[i]);
        for(int i = 0; i < n; i++) scanf("%d", &w[i]);


        vector<int> dp(m+1, 0);
        for(int i = 0; i < n; i++){
            for(int j = m; j >= 0; j--){
                if(w[i] <= j) // 由于存在物品重量为 0 的情况
                    dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
            }
        }
        printf("%d\n", dp[m]);
    }

    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

# 参考链接

背包九讲 (opens new window)

编辑

上次更新: 2025/05/21, 06:42:57

← KMP算法完全背包→