数据结构算法笔记|10 动态规划

10.1 动态规划解题步骤

  1. 确定dp数组以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

10.2 0-1背包

10.2.1 价值最大问题

问题

有n件物品和最多能背重量为W的背包，第i件物品重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

暴力解法

用回溯遍历取与不取，时间复杂度o(2^n)。

动态规划思路1：二维数组法

  1. 确定dp数组以及下标的含义

    二维数组dp[i][j]

    含义：[0,i]之间的物品任取，放到容量为j的背包中，所能得到的最大价值。

  2. 确定递推公式

    不放物品i：dp[i-1][j]

    放物品i：dp[i-1][j-weight[i]]+value[i]

    递推公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])

  3. dp数组如何初始化

    不放物品i：由表格上方元素推出

    放物品i：由表格左上方元素推出

    初始化：

    ​ 最上一行，从物品0的重量开始，初始化为物品0的价值

    ​ 最左一列，背包容量为0，价值为0

    重量0 重量1 重量2 重量3
    物品0 0 15 15 15
    物品1 0
    物品2 0

  4. 确定遍历顺序

    通常先遍历物品，再遍历背包（只要上方和左上方有值即可，因此可以颠倒）

  5. 举例推导dp数组

动态规划思路2：一维数组法

总体思路：把上一层拷贝到当前层，直接使用一层数组更新

  1. 确定dp数组以及下标的含义

    一维数组dp[j]：容量为j的背包所能容纳物品的最大价值

  2. 确定递推公式

    dp[j] = max(dp[j], dp[j-weight[i]]+value[i])

  3. dp数组如何初始化

    dp[0]=0

  4. 确定遍历顺序

    先遍历物品，再倒序遍历背包

    倒序的必要性：一维数组法相当于二维数组的当前层重复利用了上一层的空间，正序遍历会先把后面要用到的dp[j-weight[i]]更新，导致后续数组更新时会取不到想要的，原先二维数组对应的左上角的旧值

    1
    2
    3
    4
    for(i = 0; i < 物品数量; i++){
    	for(j = bagweight; j >= weight[i];j--){
    	}
    }

  5. 举例推导dp数组

​ dp[2]=dp[2-1]+15=15

​ dp[1]=dp[1-1]+15=15

例题

以卡码网46题为例

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。

第三行包含 M 个正整数，代表每种研究材料的价值。

输出

输出一个整数，代表小明能够携带的研究材料的最大价值。

题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int M, N;
  cin >> M;
  cin >> N;
  vector<int> weight(M), value(M);
  for (int i = 0; i < M; i++) {
    cin >> weight[i];
  }
  for (int j = 0; j < M; j++) {
    cin >> value[j];
  }
  int dp[N+1] = {0};
  for (int j = 0; j < M; j++) {
    for (int i = N; i >= weight[j]; i--) {
      dp[i] = max(dp[i], dp[i - weight[j]] + value[j]);
    }
  }
  cout << dp[N];
  return 0;
}

注意：重量，价值和空间均从0编号，但根据物理含义，重量和价值的最大下标是M-1，空间的最大下标是N.

10.2.2 背包装满问题

问题

用nums装满容量为x的背包，有几种方法

动态规划思路1：二维数组法

  1. 确定dp数组以及下标的含义

    二维数组dp[i][j]

    含义：[0,i]之间的物品任取，放到容量为j的背包中，能装满的方法。

  2. 确定递推公式

    不放物品i：dp[i-1][j]

    放物品i：dp[i-1][j-weight[i]]

    递推公式：放i和不放i的方法数之和 dp[i][j] = dp[i-1][j]+dp[i-1][j-weight[i]]

  3. dp数组如何初始化

    数组第一行，恰好能放下物品0时方法为1：dp[0][nums[0]]=1

    数组第一列， 装满容量为0的空间的方法：dp[i][0]=2^t, t表示重量为0的物品的数目

  4. 确定遍历顺序

    通常先遍历物品，再遍历背包（只要上方和左上方有值即可，因此可以颠倒）

  5. 举例推导dp数组

动态规划思路2：一维数组法

递推公式：dp[j] += dp[j-weight[i]]

例题

以Leetcode - 494为例

题目

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

思路

设加法总和为x，则有x-(sum-x)=target，即x=(sum+target)/2

问题转化成背包装满容量为(sum+target)/2的背包，根据定义有sum < |target|，且(sum+target)/2为整数。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int len = nums.size(), sum = 0, result = 0;
        for(int i = 0; i < len; i++){
            sum += nums[i];
        }

        if(sum < abs(target) || (sum+target)%2 == 1) return 0;

        vector<int> dp((sum+target)/2+1, 0);
        dp[0] = 1;

        for(int i = 0; i < len; i++){
            for(int j = (sum+target)/2; j >= nums[i]; j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[(sum+target)/2];
    }
};

注意：明确定义背包容量和物品属性，并在遍历之前排除不符合条件的情况。

10.2 完全背包

动态规划：二维数组法

递推公式

​ 不放物品i: dp[i-1][j]

​ 放物品i: 背包物品无限，因此是在物品i和容量j-weight的价值基础上增加价值 dp[i][j-weight[i]]+value[i]

​ 递推公式: dp[i][j]=max(dp[i-1][j], dp[i][j-weight[i]]+value[i])

初始化

​ 背包物品无限，因此物品0可以根据容量无限添加

遍历顺序

​ 求组合数外层遍历物品，求排列数外层遍历背包

例题

以卡码网52题为例

问题

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。

小明的行李箱所能承担的总重量是有限的，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。

输入

第一行包含两个整数，n，v，分别表示研究材料的种类和行李所能承担的总重量

接下来包含 n 行，每行两个整数 wi 和 vi，代表第 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
# include <iostream>
# include <vector>
using namespace std;

int main(){
    int n,v;
    cin>>n; // 物品种类
    cin>>v; // 背包容量
    vector<int> weight(n), value(n);
    for(int i = 0; i < n; i++){
        cin>>weight[i];
        cin>>value[i];
    }
    vector<vector<int>> dp(n, vector<int>(v+1,0));
    for(int j = weight[0]; j < v+1; j++){
        dp[0][j] = dp[0][j-weight[0]]+value[0];
    }
    for(int i = 1; i < n; i++){
        for(int j = 0; j < v+1; j++){
            if(j >= weight[i])
                dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]]+value[i]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout<<dp[n-1][v];
    return 0;
}

注意：由于i=0已经初始化，且递推公式定义要求i>1，因此遍历时从i=1开始

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

int main(){
    int n,v;
    cin>>n; // 物品种类
    cin>>v; // 背包容量
    vector<int> weight(n), value(n);
    for(int i = 0; i < n; i++){
        cin>>weight[i];
        cin>>value[i];
    }
    vector<int> dp(v+1,0);

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