动态规划算法 ╰半夏微凉° 2022-11-13 05:28 240阅读 0赞 # 一:动态规划算法 # ## 1:动态规划算法介绍 ## 1) 动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解 的处理算法 2) 动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这 些子问题的解得到原问题的解。 3) 与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。 ( 即下一个子 阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解 ) 4) 动态规划可以通过填表的方式来逐步推进,得到最优解. ## 2:应用场景\-背包问题 ## 背包问题:有一个背包,容量为 4 磅 , 现有如下物品 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70][] 1. 要求达到的目标为装入的背包的总价值最大,并且重量不超出 2. 要求装入的物品不能重复 思路分析和图解 3. 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品,如何选择物品放入背包使物品的价值最大。其中又分 **01** **背包** 和 **完全背包** ( 完全背包指的是:每种物品都有无限件可用 ) 4. 这里的问题属于 **01** **背包** ,即每个物品最多放一个。而无限背包可以转化为 01 背包。 5. 算法的主要思想,利用动态规划来解决。每次遍历到的第 i 个物品,根据 w\[i\] 和 v\[i\] 来确定是否需要将该物品放入背包中。即对于给定的 n 个物品,设 v\[i\] 、 w\[i\] 分别为第 i 个物品的价值和重量, C 为背包的容量。再令 v\[i\]\[j\]表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值。则我们有下面的结果: (1) v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是 0 (2) 当 w[i]> j 时:v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于 当前背包的容量时,就直接使用上一个 单元格的装入策略 (3) 当 j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} // 当 准备加入的新增的商品的容量小于等于当前背包的容量, // 装入的方式: v[i-1][j]: 就是上一个单元格的装入的最大值 v[i]: 表示当前商品的价值 v[i-1][j-w[i]]: 装入 i-1 商品,到剩余空间 j-w[i]的最大值 当 j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}: 图解的分析 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1][] 3:代码实现 package com.dynamic; /** * @author lizhangyu * @date 2021/3/27 23:16 */ public class KnapsackProblem { public static void main(String[] args) { //物品的重量 int[] w = {1, 4, 3}; //物品的价值 int[] val = {1500, 3000, 2000}; //背包的容量 int m = 4; //物品的个数 int n = val.length; //创建二维数组,v[i][j]表示在前i个物品中能够装入容量为j的背包的最大价值 int[][] v = new int[n+1][m+1]; //为了记录放入商品的情况,我们定一个二维数组 int[][] path = new int[n+1][m+1]; for (int i = 0; i < v.length; i++) { //将第一列设置为0 v[i][0] = 0; } for (int j = 0; j < v[0].length; j++) { //将第一行设置为0 v[0][j] = 0; } //不处理第一行 for (int i = 1; i < v.length; i++) { //不处理第一列 for (int j = 1; j < v[0].length; j++) { if (w[i-1] > j) { v[i][j] = v[i-1][j]; }else { // v[i][j] = Math.max(v[i-1][j], val[i-1] + v[i-1][j-w[i-1]]); if (v[i-1][j] < val[i-1] + v[i-1][j-w[i-1]]) { v[i][j] = val[i-1] + v[i-1][j-w[i-1]]; //把当前的情况记录到path path[i][j] = 1; }else { v[i][j] = v[i-1][j]; } } } } //输出下v看看目前的情况 for (int i = 0; i < v.length; i++) { for (int j = 0; j < v[i].length; j++) { System.out.print(v[i][j] + " "); } System.out.println(); } System.out.println("========================="); for (int i = 0; i < path.length; i++) { for (int j = 0; j < path[i].length; j++) { if (path[i][j] == 1) { System.out.printf("第%d 个商品放入到背包\n", i); } } } System.out.println("装入背包最大价值的物品:=>"); //行的最大下标 int i = path.length - 1; //列的最大下标 int j = path[0].length - 1; while (i > 0 && j > 0) { if (path[i][j] == 1) { System.out.printf("第%d 个商品放入到背包\n", i); j-=w[i-1]; } i--; } } } 运行结果如下: 0 0 0 0 0 0 1500 1500 1500 1500 0 1500 1500 1500 3000 0 1500 1500 2000 3500 ========================= 第1 个商品放入到背包 第1 个商品放入到背包 第1 个商品放入到背包 第1 个商品放入到背包 第2 个商品放入到背包 第3 个商品放入到背包 第3 个商品放入到背包 装入背包最大价值的物品:=> 第3 个商品放入到背包 第1 个商品放入到背包 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70]: /images/20221022/e3d1ee1353c74c68bee9da2f5bb7b05a.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1]: /images/20221022/a3696c63b56e41bb8e920736cdbc0be6.png
还没有评论,来说两句吧...