最为基础的DP模板 但真的无论过了多久都会忘掉

背包问题

01背包问题

最基础的DP问题 选择模型

f[i][j] 表示选前i个物品 体积不超过j的物品的最大价值
不选当前物品的集合为 f[1…i-1][j] 其最大值为 max(f[1… i-1])
选取当前物体的集合的最大值 f[i - 1][j - v[i]] + w[i] (从集合的体积中除去当前物品的体积 并加上当前物体的最大值)
原题链接:
https://www.acwing.com/problem/content/2/

  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
    #include<iostream>
    #include<algorithm>
    using namespace std;

    const int N = 1010;
    int w[N],v[N]; // 价值与体积
    int f[N][N];    // f[i][j] 前i个物体中 体积不超过j的物品的价值最大值
    int n,m;    // 物品件数n 与背包容量m

    int main(){
        cin >> n >> m;
        // 读入数据
        for(int i = 1 ; i <= n ; i++){
            cin>>v[i] >> w[i];
        }
        
        for(int i = 1; i <= n ; i++){
            for(int j = 0; j <= m ; j++){
                // 最大值为 前i - 1物品 即不选的最大值
                f[i][j] = f[i -1][j];
                // 最大值为 选了当前位置的最大值
                if(j >= v[i]){
                    f[i][j]  = max(f[i][j],f[i - 1][j - v[i]] + w[i]);    
                }
            }
        }
        
        cout << f[n][m];
        return 0;
    }

  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
    #include<iostream>
    #include<algorithm>
    using namespace std;

    const int N = 1010;
    int w[N],v[N]; // 价值与体积
    int f[N];    // f[i][j] 前i个物体中 体积不超过j的物品的价值最大值
    int n,m;    // 物品件数n 与背包容量m

    int main(){
        cin >> n >> m;
        // 读入数据
        for(int i = 1 ; i <= n ; i++){
            cin>>v[i] >> w[i];
        }
        
        for(int i = 1; i <= n ; i++){
            for(int j = m; j >=v[i] ; j--){
                // 最大值为 前i - 1物品 即不选的最大值
                // 进行1维优化后 该步仍然等价
                //f[i][j] = f[i -1][j]; -> f[i] = f[i]
                
                // 最大值为 选了当前位置的最大值
                    // f[i][j]  = max(f[i][j],f[i - 1][j - v[i]] + w[i]); 
                    // -> f[i] = max(f[i] , f[j - v[i]] + w[i])
                    // 此步优化为1维后 如果是从小到大计算j 那么j - v[i] 一定是小于j的 
                    // 即j-v[i] 是先被计算出来 即此时j-v[i] 是第i层的j-v[i]
                    // 即进行一维转换 等价于 f[i][j - v[i]] 而不是f[i -1][j - v[i]] 即结果与原式不等价
                    // 所以只需改变循环顺序 从大到小枚举 那么此时 j-v[i] 对应的上一层就是f[i - 1]
                    f[j] = max(f[j], f[j - v[i]] + w[i]);
            }
        }
        
        cout << f[m];
        return 0;
    }

完全背包问题

完全背包问题代码上与01背包区别很小 但实际分析思路却区别很大
完全背包问题中每件物品可以取无限次而不是1次

  1. 状态表示: f[i][j] 表示从前i个物品中选 总体积不大于j的 最大值
  2. 状态计算: 同样与01背包问题相同的思路可以进行两种状态的划分
    1. 不取当前物体的集合 f[i - 1][0 …. j] 其最大值即为 max(f[i - 1][j])
    2. 取当前物体的集合
      f[i][j] = max(f[i - 1][j],f[i -1][j -v] + w, f[i - 1][j - 2v] + 2w, ….)
      f[i][j - v] = max(f[i -1][j -v], f[i - 1][j - 2v] + w, f[i - 1][j - 3v] + 2w, …)
      上面两式子合并可得
      f[i][j] = max(f[i - 1][j] , f[i][j - v] + w)

原题链接:
https://www.acwing.com/problem/content/3/

  1. 朴素二维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
    #include<iostream>
    using namespace std;

    const int N = 1010;

    int v[N],w[N];
    int f[N][N];    // 取前i个物品的集合中 体积小于j的集合最大值
    int n,m;

    int main(){
        cin >> n >> m;
        
        for(int i = 1 ; i <= n ; i++){
            cin >> v[i] >> w[i];
        }
        
        for(int i = 1  ; i <= n ; i++ ){
            for(int j = 0 ; j <= m ; j++){
                // 第一部分一定存在 即不取第i件物品最大值 等于之前所有不取第i件物品的集合的最大值
                f[i][j] = f[i - 1][j];
                
                // 第二部分的最大值 当选择取第i件物品时 
                // 当前物品件数可以取
                if(j >= v[i]){
                    f[i][j] = max(f[i][j],f[i][j - v[i]] + w[i]);
                }
            }
        }
        
        cout<< f[n][m];
        
        return 0;
    }

  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
#include<iostream>
using namespace std;

const int N = 1010;

int v[N],w[N];
int f[N];    // 取前i个物品的集合中 体积小于j的集合最大值
int n,m;

int main(){
    cin >> n >> m;
    
    for(int i = 1 ; i <= n ; i++){
        cin >> v[i] >> w[i];
    }
    
    for(int i = 1  ; i <= n ; i++ ){
        for(int j = v[i] ; j <= m; j++){
            // 第一部分一定存在 即不取第i件物品最大值 等于之前所有不取第i件物品的集合的最大值
            
            // 进行1维优化后  改步保持不变即可忽略
            // f[j] = f[j];
            
            // 第二部分的最大值 当选择取第i件物品时 
            // 当前物品件数可以取
            
                // f[i][j] = max(f[i][j],f[i][j - v[i]] + w[i]);
                // -> f[j] = max(f[j],f[j - v[i]] + w[i]);
                // j 从小到大开始枚举 因此j - v[i] < j 在上一层已经被计算过 故j直接从大到小枚举即可
            f[j] = max(f[j],f[j  - v[i]] + w[i]);
        }
    }
    
    cout<< f[m];
    
    return 0;
}