devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

动态规划（Dynamic-Programming）问题讲解

作者：我家自动化 | 2024-06-24 02:51:40

赞

踩

动态规划（Dynamic-Programming）问题讲解

动态规划类问题

  • 从已知子问题的解，推导出当前问题的解 推导过程可以表达为一个数学公式
  • 用一维或二维数组来保存之前的计算结果（可以进一步降维优化）

        将当前问题 分解成子问题 ，找出递归公式，分阶段进行求解 求解过程中缓存子问题的解，避免重复计算。

以一个简单例子Fibonacci数列为例，求Fibonacci数列第 n 项的

从第二项开始，每一项的值都等于前两项的值之和
0 1 1 2 3 5 8
dp[i] = dp[i-1] + dp[i-2]

思路：

        1.若求第 0 项或第 1 项的值，直接返回对应的值 0 或 1

        2.创建一个一维数组缓存第n项数值之前的求解结果，并初始化第一项和第二项的值

        3.使用循环计算处每一项的值，直到第 n 项，最后返回一维数组的第n项值即可

代码：

  1. public static int fibonacci(int n) {
  2.         if (n == 0) {
  3.             return 0;
  4.         } else if (n == 1) {
  5.             return 1;
  6.         }
  7.         int[] dp = new int[n + 1];
  8.         dp[0] = 0;
  9.         dp[1] = 1;
  10.         for (int i = 2; i <= n; i++) {
  11.             dp[i] = dp[i - 1] + dp[i - 2];
  12.         }
  13.         return dp[n];
  14. }

测试：

  1. public static void main(String[] args) {
  2.         // 0 1 1 2 3 5 8
  3.         System.out.println(fibonacciDown(13)); //求第 7 项值
  4. }

降维优化：对于每个子问题只需要三个值参与，何不用三个变量代替一维数组进行优化：

  1.     /**
  2.      * 求 Fibonacci 的第 n 项 (降维)
  3.      *
  4.      * @param n 第几项
  5.      * @return
  6.      */
  7.     public static int fibonacciDown(int n) {
  8.         if (n == 0) {
  9.             return 0;
  10.         } else if (n == 1) {
  11.             return 1;
  12.         }
  13.  
  14.         int a = 0, b = 1;
  15.         for (int i = 2; i <= n; i++) {
  16.             int c = a + b; //记录第i项的值
  17.             //更新值    
  18.             a = b;
  19.             b = c;
  20.         }
  21.         return b;
  22.     }

Leecode62. 不同路径 题

从start走到finish有多少种走法（只能向右或向下走）

 将每个格子的走法都记录出来，标识数字为 start 到该格子上的有多少走法，，找出规律

可看出规律为：dp[i][j] = dp[i][j - 1] + dp[i -1][j]，并且第一行和第一列的值都为1，即走法只有一种

思路：

        1.以一个二维数组缓存每个格子的走法数

        2.遍历每行每列，求出每个格子的走法数

        3.最后返回第m行第n列的值，即为最终结果

代码：

  1.     /**
  2.      * 求到第m行n列有多少种走法，只能向右和向下
  3.      *
  4.      * @param m
  5.      * @param n
  6.      * @return
  7.      */
  8.     public static int uniquePaths2(int m, int n) {
  9.         int[][] dp = new int[m][n];
  10.         //初始化第一行和第一列的值为 1（其走法只有一种）
  11.         for (int i = 0; i < m; i++) {
  12.             dp[i][0] = 1;
  13.         }
  14.         for (int i = 0; i < n; i++) {
  15.             dp[0][i] = 1;
  16.         }
  17.         for (int i = 1; i < m; i++) {
  18.             for (int j = 1; j < n; j++) {
  19.                 dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
  20.             }
  21.         }
  22.         print(dp);
  23.         return dp[m - 1][n - 1];
  24.     }

降维优化：

每次计算当前格子的走法数时，只需要上一个格子和左边格子的走法之和，何不使用一维数组，上一个格子的走法即为当前格子的做法，将dp[i][j] = dp[i][j - 1] + dp[i -1][j]改为dp[j] = dp[j] + dp[j - 1]，实现降维优化的目的，以第二行到第三行为例：

代码：

  1.     /**
  2.      * 求到第m行n列有多少种走法，只能向右和向下 (降维，二维 变 一维)
  3.      *
  4.      * @param m
  5.      * @param n
  6.      * @return
  7.      */
  8.     public static int uniquePaths(int m, int n) {
  9.         int[] dp = new int[n];
  10.         //初始化第一行和第一列的值为 1（其走法只有一种）
  11.         Arrays.fill(dp, 1);
  12.         for (int i = 1; i < m; i++) {
  13.             for (int j = 1; j < n; j++) {
  14.                 dp[j] = dp[j] + dp[j - 1]; //自己加上 上一列的
  15.             }
  16.         }
  17. //        System.out.println(Arrays.toString(dp));
  18.         return dp[n - 1];
  19.     }

2. 01背包问题 - AcWing题库

从N个物体中选择物体放入体积为V的背包中，使得价值最大，每种物品只能选择一次

以一下测试示例：

  1. 4 5    //物体数量为 4，背包体积为 5
  2. 1 2   //第一个物体的体积 1 和价值 2
  3. 2 4
  4. 3 4
  5. 4 5

以一个二维数组缓存第一行只有物品A的选择，第二行只有物体A、B时的选择等..，

ABCD分别表示四个物体

二维数组 dp 中：

第一行中选择物体A，体积为1，在体积为0时不能放下为0，其它都能放下A

第二行中选择物体B，体积为2，在背包体积为0、1时不能放下，将上一行数据复制下来，背包体积为2时能放下，价值为2比上一行的A更大，为3、4、5时可以放下B此外还能放下一个物体A

第三行中选择物体C，体积为3，在背包体积为0、1、2时不能放下，将上一行数据复制下来，在背包体积 为3是虽然能放下C，但是上一行的BA价值是6，比C的价值大，所以直接复制下来，在体积为5时，当前背包除了能放下BA外还能放下一个C

第四行选择物体D，体积为4，在背包体积为0、1、2、3时不能放下，将上一行数据复制下来，在背包体积 为4是虽然能放下D，但是上一行的BA价值是6，比D的价值大，所以直接复制下来，在体积为5时同理

  1.             编号 体积(g)  价值(元)     物品名
  2.             1     1         2         A
  3.             2     2         4         B
  4.             3     3         4         C
  5.             4     4         5         D
  6. 二维数组 dp ：
  7.            0   1   2   3   4    5  --> 背包体积
  8.         0  0   A   A   A   A    A       A
  9.         1  0   A   B   BA  BA   BA      B
  10.         2  0   A   B   BA  BA   BAC     C
  11.         3  0   A   B   BA  BA   BAC     D
  12.  
  13.         0, 2, 2, 2, 2, 2
  14.         0, 2, 4, 6, 6, 6
  15.         0, 2, 4, 6, 6, 8
  16.         0, 2, 4, 6, 6, 8
  17.         结果：8 (BAC)

总结一个规律：

1.装得下 —— 当前物品价值比上一行价值更大时，选择当前物品，再加上总体积 - 当前物品体积得到的体积值列中最大价值得物品，加到当前处
    dp[i][j] = Math.max(dp[i-1][j],currItemValue + dp[i-1][jTotal - currItem.weight]) 比如dp数组中：dp[1][3] = Max(dp[0][3],B + dp[0][3-2]) = BA
2.装不下,将上一行物品复制下来
    dp[i][j] = dp[i-1][j]

代码二维：

  1. import java.util.Scanner;
  2.  
  3. /**
  4.  * 0 - 1背包问题
  5.  */
  6. public class Main {
  7.        public static void main(String[] args) {
  8. /*
  9.             编号 体积(g)  价值(元)     物品名
  10.             1     1         2         A
  11.             2     2         4         B
  12.             3     3         4         C
  13.             4     4         5         D
  15.            0   1   2   3   4    5  --> 体积
  16.         0  0   A   A   A   A    A       A
  17.         1  0   A   B   BA  BA   BA      B
  18.         2  0   A   B   BA  BA   BAC     C
  19.         3  0   A   B   BA  BA   BAC     D
  21.         0, 2, 2, 2, 2, 2
  22.         0, 2, 4, 6, 6, 6
  23.         0, 2, 4, 6, 6, 8
  24.         0, 2, 4, 6, 6, 8
  25.         结果：8 (BAC)
  26.         1.装得下 —— 当前物品价值比上一行价值更大时，选择当前物品，再加上总体积 - 当前物品体积量得到得体积列中最大价值得物品，加到当前处
  27.             dp[i][j] = Max(dp[i-1][j],currItemValue + dp[i-1][jTotal - currItem.weight]) 比如：dp[3][8] = Max(dp[2][8],D + dp[2][8-1]) = DA
  28.         2.装不下,将上一行物品复制下来
  29.             dp[i][j] = dp[i-1][j]
  30.  */
  31.         Scanner sc = new Scanner(System.in);
  32.         int N = sc.nextInt(); //物品数量
  33.         int V = sc.nextInt(); //背包容积
  34.  
  35.         int[] vArr = new int[N]; //N个物品的体积
  36.         int[] pArr = new int[N]; //N个物品的价值
  37.         for (int i = 0; i < N; i++) {
  38.             vArr[i] = sc.nextInt();
  39.             pArr[i] = sc.nextInt();
  40.         }
  41.  
  42.         System.out.println(knapsackProblem01(V, vArr, pArr, N));
  43.     }
  44.  
  45.     public static int knapsackProblem01(int V, int[] vArr, int[] pArr, int N) {
  46.         int[][] dp = new int[N][V + 1];
  47.  
  48.         for (int j = 0; j < V + 1; j++) {
  49.             if (vArr[0] <= j) { //装得下
  50.                 dp[0][j] = pArr[0];
  51.             }
  52.         }
  53.         for (int i = 1; i < N; i++) {
  54.             for (int j = 0; j < V+1; j++) {
  55.                 int x = dp[i - 1][j]; //上一行的价值
  56.                 if (vArr[i] <= j) { //装得下
  57.                     //                      当前物品价值      剩余物品价值
  58.                     dp[i][j] = Math.max(x, pArr[i] + dp[i-1][j - vArr[i]]);
  59.                 } else { //装不下
  60.                     dp[i][j] = x;
  61.                 }
  62.             }
  63.         }
  64.         return dp[N - 1][V];
  65.     }
  66.  
  67. }

 代码（降维成一维数组）：

  1.     public static void main(String[] args) {
  2.         Scanner sc = new Scanner(System.in);
  3.         int N = sc.nextInt(); //物品数量
  4.         int V = sc.nextInt(); //背包容积
  5.  
  6.         int[] vArr = new int[N]; //N个物品的体积
  7.         int[] pArr = new int[N]; //N个物品的价值
  8.         for (int i = 0; i < N; i++) {
  9.             vArr[i] = sc.nextInt();
  10.             pArr[i] = sc.nextInt();
  11.         }
  12.  
  13.         int[] dp = new int[V + 1];
  14.  
  15.         for (int j = 0; j < V + 1; j++) {
  16.             if (vArr[0] <= j) { //装得下
  17.                 dp[j] = pArr[0];
  18.             } else { //装不下
  19.                 dp[j] = 0;
  20.             }
  21.         }
  22.         //System.out.println(Arrays.toString(dp));
  23.         for (int i = 1; i < N; i++){
  24.             for (int j = V; j > 0; j--) {
  25.                 if (vArr[i] <= j) { //装得下
  26.                     //     pArr[i]当前物品价值   dp[j - vArr[i]]剩余空间在上次中（避免同一物品重复使用）能装的最大值
  27.                     dp[j] = Math.max(dp[j], pArr[i] + dp[j - vArr[i]]);
  28.                 }
  29.             }
  30.             //System.out.println(Arrays.toString(dp));
  31.         }
  32.  
  33.         System.out.println(dp[V]);
  34.     }

3. 完全背包问题 - AcWing题库

与01背包问题的区别：

dp[i][j] = Math.max(x, pArr[i] + dp[i][j - vArr[i]]); //完全背包中物品数量无限，从本次物品中找，同一物品可重复使用

dp[i][j] = Math.max(x, pArr[i] + dp[i-1][j - vArr[i]]); //01背包中物品数量只有一个，从上次物品中找，同一物品只能用一次

代码（二维）：

  1. import java.util.Scanner;
  2.  
  3. /**
  4.  * 完全背包问题
  5.  */
  6. public class Main {
  7.    public static void main(String[] args) {
  8. /*
  9.             编号 体积(g)  价值(元)     物品名
  10.             1     1         2         A
  11.             2     2         4         B
  12.             3     3         4         C
  13.             4     4         5         D
  15.         完全背包：
  16.            0   1   2    3       4       5  --> 体积
  17.         0  0   A   AA   AAA     AAAA    AAAAA       A
  18.         1  0   A   B    BA      BB      BBA         B
  19.         2  0   A   B    BA      BB      BBA         C
  20.         3  0   A   B    BA      BB      BBA         D
  22.       0      2      4      6      8     10      A
  23.       0      2      4      6      8     10      B
  24.       0      2      4      6      8     10      C
  25.       0      2      4      6      8     10      D
  26.         结果：10 (BAC)
  27.         1.装得下 —— 当前物品价值比上一行价值更大时，选择当前物品，再加上(总体积 - 当前物品体积)得到的体积列中最大价值得物品，加到当前处
  28.             dp[i][j] = Max(dp[i-1][j],currItemValue + dp[i-1][jTotal - currItem.weight]) 比如：dp[3][8] = Max(dp[2][8],D + dp[2][8-1]) = DA
  29.         2.装不下,将上一行物品复制下来
  30.             dp[i][j] = dp[i-1][j]
  31.  */
  32.         Scanner sc = new Scanner(System.in);
  33.         int N = sc.nextInt(); //物品数量
  34.         int V = sc.nextInt(); //背包容积
  35.  
  36.         int[] vArr = new int[N]; //N个物品的体积
  37.         int[] pArr = new int[N]; //N个物品的价值
  38.         for (int i = 0; i < N; i++) {
  39.             vArr[i] = sc.nextInt();
  40.             pArr[i] = sc.nextInt();
  41.         }
  42.  
  43.         System.out.println(knapsackProblemComplete(V, vArr, pArr, N));
  44.     }
  45.  
  46.  
  47.     public static int knapsackProblemComplete(int V, int[] vArr, int[] pArr, int N) {
  48.         int[][] dp = new int[N][V + 1];
  49.  
  50.         for (int j = 0; j < V + 1; j++) {
  51.             if (vArr[0] <= j) { //装得下
  52.                 dp[0][j] = pArr[0] + dp[0][j - vArr[0]];
  53.             }
  54.         }
  55.         for (int i = 1; i < N; i++) {
  56.             for (int j = 0; j < V + 1; j++) {
  57.                 int x = dp[i - 1][j]; //上一行的价值
  58.                 if (vArr[i] <= j) { //装得下
  59.                     //                    当前物品价值      剩余体积的物品价值（从本次中找）
  60.                     dp[i][j] = Math.max(x, pArr[i] + dp[i][j - vArr[i]]);
  61.                 } else { //装不下
  62.                     dp[i][j] = x;
  63.                 }
  64.             }
  65.         }
  66.         return dp[N - 1][V];
  67.     }
  68. }

降维：

  1. import java.util.Scanner;
  2.  
  3. /**
  4.  * 完全背包问题
  5.  */
  6. public class Main {
  7.    public static void main(String[] args) {
  8. /*
  9.         1. n个物品都是固体，有重量和价值
  10.         2. 现在你要取走不超过 10克 的物品
  11.         3. 每件物品只能使用一次
  13.             编号 体积(g)  价值(元)     物品名
  14.             1     1         2         A
  15.             2     2         4         B
  16.             3     3         4         C
  17.             4     4         5         D
  19.         完全背包：
  20.            0   1   2    3       4       5  --> 体积
  21.         0  0   A   AA   AAA     AAAA    AAAAA       A
  22.         1  0   A   B    BA      BB      BBA         B
  23.         2  0   A   B    BA      BB      BBA         C
  24.         3  0   A   B    BA      BB      BBA         D
  26.       0      2      4      6      8     10      A
  27.       0      2      4      6      8     10      B
  28.       0      2      4      6      8     10      C
  29.       0      2      4      6      8     10      D
  30.         结果：10 (BAC)
  31.         1.装得下 —— 当前物品价值比上一行价值更大时，选择当前物品，再加上总重量 - 当前物品重量得到得重量列中最大价值得物品，加到当前处
  32.             dp[i][j] = Max(dp[i-1][j],currItemValue + dp[i-1][jTotal - currItem.weight]) 比如：dp[3][8] = Max(dp[2][8],D + dp[2][8-1]) = DA
  33.         2.装不下,将上一行物品复制下来
  34.             dp[i][j] = dp[i-1][j]
  35. 4 5
  36. 1 2
  37. 2 4
  38. 3 4
  39. 4 5
  40.  */
  41.         Scanner sc = new Scanner(System.in);
  42.         int N = sc.nextInt(); //物品数量
  43.         int V = sc.nextInt(); //背包容积
  44.  
  45.         int[] vArr = new int[N]; //N个物品的体积
  46.         int[] pArr = new int[N]; //N个物品的价值
  47.         for (int i = 0; i < N; i++) {
  48.             vArr[i] = sc.nextInt();
  49.             pArr[i] = sc.nextInt();
  50.         }
  51.  
  52.         System.out.println(knapsackProblemComplete2(V, vArr, pArr, N));
  53.     }
  54.  
  55.  
  56.  
  57.     /**
  58.      * 取total重量的物品 并且 价值最大(降维)
  59.      *
  60.      * @return 最大价值
  61.      */
  62.     public static int knapsackProblemComplete2(int V, int[] vArr, int[] pArr, int N) {
  63.         int[] dp = new int[V + 1];
  64.  
  65.         for (int j = 0; j < V + 1; j++) {
  66.             if (vArr[0] <= j) { //装得下
  67.                 dp[j] = pArr[0] + dp[j - vArr[0]];
  68.             }
  69.         }
  70.         for (int i = 1; i < N; i++) {
  71.             for (int j = 0; j < V + 1; j++) {
  72.                 int x = dp[j]; //上一行的价值
  73.                 if (vArr[i] <= j) { //装得下
  74.                     //                      当前物品价值      剩余物品价值
  75.                     dp[j] = Math.max(x, pArr[i] + dp[j - vArr[i]]);
  76.                 } else { //装不下
  77.                     dp[j] = x;
  78.                 }
  79.             }
  80. //            System.out.println(Arrays.toString(dp));
  81.         }
  82.  
  83.         return dp[V];
  84.     }
  85. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/751459
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号