动态规划的思想与应用

Java基础

浏览数:5

2019-9-11

动态规划在实际应用中十分广泛,经常在笔试中碰到动态规划的题目,而且理解起来也比较困难,灵活应用起来更加的不容易,今天就总结一下,到底在什么时候使用动态规划,以及怎么使用动态规划。

动态规划的使用场景一般包括三个特征:

   (1)最优子结构:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构。

          比如要想求棋盘两对角的最短距离,那个每走一格算一格阶段,每一格最优解必定是在上一格的最优解中得来的,也就是说每一个阶段都有最优的一个决策代表最优子解。

   (2)无后效性:某一状态一旦确定,就不受这个状态的以后的决策影响。

           后效性是指,如果上面的例子中的每一个格子的长度是不一致的,那么在当前选择的格子决策背景下,可能会对后面选择决策造成影响,如下图。

                                    

                    如果选择了当前选择了值为10的这个节点,则会导致后续只能选择100,甚至200的节点,即在选择10和20节点的时候,会对后续的决策产生影响。

   (3)有重叠子问题:子问题之间不是相互独立的,一个子问题在下一阶段的决策中可能被多次使用到。

          即当前的最优解的计算,我们只需要记录下来,在后续的比较中使用到,而不需要再次计算,增加时间复杂度。

动态规划的基本过程描述:

      每次决策依赖于当前状态,又引起状态的转移,一个决策序列就是在变化的状态中产生出来的,所以,动态规划可以看成是多阶段最优化决策来解决问题的过程。

使用动态规划解决问题,最重要的就是确定动态的三要素:

   (1)问题的阶段。

   (2)每个阶段的状态。

   (3)从前一个阶段到后一个阶段的递推关系。

下面我们看一个经典而简单的例子来阐述一下,动态规划到底怎么用来解决问题:

 1 package DP;
 2 
 3 /**
 4  * Created by jy on 2017/10/5.
 5  * 求解给定数组的子数组,使得子数组的和最大,子数组的元素在给定的数组中必须是连续的
 6  */
 7 public class MaxSumSubArray {
 8 
 9     /*dp解法:
10     * 可以令curMax[]是以当前元素结尾的最大子数组和,maxSum是全局的最大子数组和,
11     * 当往后扫描时,对第j个元素有两种选择:要么放入前面找到的子数组,要么做为新子数组的第一个元素
12     * 举个例子,当输入数组是1, -2, 3, 10, -4, 7, 2, -5,那么,currSum和maxSum相应的变化为:
13     *
14     * j(前j个元素): 0    1     2    3     4    5     6     7     8
15     * currSum[] :  0   1     -1    3    13    9    16    18    13
16     * maxSum[]  :  0   1     1     3    13    13   16    18    18
17     *
18     *
19     * 1.起始阶段(i=0),max = nums[0];
20     * 2.第i(i > 0)个阶段,max = curMax[i],curMax是第i个阶段的最大子序列和;
21     * 3.第i-1和第i个阶段的关系,curMax[i] = Math.max(curMax[i - 1] + nums[i], nums[i]);
22     * 4.根据前面动态规划的定义,则最大子序列和max = Math.max(max, curMax[i])
23     * */
24     public static int DpMaxSubArray(int[] nums) {
25         //curMax是当前的最大子序列和
26         int[] curMax = new int[nums.length];
27         //起始阶段
28         curMax[0] = nums[0];
29         //刻画最优解
30         int max = nums[0];
31         for (int i = 1; i < nums.length; i++) {
32             //每一阶段的最优都有上一阶段的最优的基础上而来
33             curMax[i] = Math.max(curMax[i - 1] + nums[i], nums[i]);
34             System.out.print(curMax[i] + " ");
35             max = Math.max(max, curMax[i]);
36         }
37         return max;
38     }
39 }

 通常动态规划都有一个阶段的概念,在这里的阶段就是前多少个元素,求前两个元素的最大子数组就是一个阶段,求前三个元素的最大子数组是一个阶段……每一个阶段的最优解都放在一个数组里记录,用于在下一阶段中比较,

在这个问题中,如果第n-1 阶段的最大和比第n个元素还要小,则当前的第n个元素作为最优子结构(最大和子数组)的开头第一个元素,继续往后扫描,而最大和就在currMax[i]中产生。

   我们再来看看一个经典的0-1背包问题:

求解背包问题:
* 给定 n 个物品,其重量分别为 w1,w2,……,wn, 价值分别为 v1,v2,……,vn
* 要放入总承重为 totalWeight 的箱子中,
* 求可放入箱子的背包价值总和的最大值。
 1 class ZeroOneProblem {
 2 
 3     //定义背包为item集合,item有两个属性,一个是weight,一个是value
 4     private Item[] item;
 5 
 6     //总重量
 7     private int totalWeight;
 8 
 9     //物品数量
10     private int n;
11 
12     //装n个物品,总重量为totalWeight的最优解
13     private int[][] bestValues;
14 
15     //装n个物品,总重量为totalWeight的最优值
16     private int bestValue;
17 
18     //装n个物品,总重量为totalWeight的最优时的物品组成
19     private ArrayList<Item> bestSolution;
20     
21     // 求解前 n 个背包、给定总承重为 totalWeight 下的背包问题
22     public void solve() {
23         System.out.println("给定物品:");
24         for (Item item : item) {
25             System.out.println(item);
26         }
27         System.out.println("给定总承重: " + totalWeight);
28         //i为0时,表示没有物品,j为0时表示没有重量
29         for (int j = 0; j <= totalWeight; j++) {
30             for (int i = 0; i <= n; i++) {
31                 if (i == 0 || j == 0) {
32                     bestValues[i][j] = 0;
33                 } else {
34                     // 如果第 i 个物品重量大于此时的剩下的承重,则最优解存在于前 i-1 个物品中,第i个物品不放进去
35                     // 第 i 个物品是 item[i-1]
36                     if (j < item[i - 1].getWeight()) {
37                         bestValues[i][j] = bestValues[i - 1][j];
38                     } else {
39                         // 如果第 i 个物品不大于总承重,则最优解要么是包含第 i 个物品的最优解,
40                         // 要么是不包含第 i 个物品的最优解, 取两者最大值。
41                         // 第 i 个物品的重量 iweight 和价值 ivalue
42                         int iweight = item[i - 1].getWeight();
43                         int ivalue = item[i - 1].getValue();
44                         bestValues[i][j] =
45                                 Math.max(bestValues[i - 1][j], ivalue + bestValues[i - 1][j - iweight]);
46                     }
47                 }
48             }
49         }
50 
51         // 回溯:求解背包组成
52         if (bestSolution == null) {
53             bestSolution = new ArrayList<Item>();
54         }
55         int tempWeight = totalWeight;
56         for (int i = n; i >= 1; i--) {
57             if (bestValues[i][tempWeight] > bestValues[i - 1][tempWeight]) {
58                 bestSolution.add(item[i - 1]);  // item[i-1] 表示第 i 个物品
59                 tempWeight -= item[i - 1].getWeight();
60             }
61             if (tempWeight == 0) {
62                 break;
63             }
64         }
65         bestValue = bestValues[n][totalWeight];
66     }

  如果还是理解不了具体是怎么做的,可以看下面的决策表的生成过程 ,物品如下:

[weight: 2 value: 13]
[weight: 1 value: 10]
[weight: 3 value: 24]
[weight: 2 value: 15]
[weight: 4 value: 28]
[weight: 5 value: 33]
[weight: 3 value: 20]
[weight: 1 value: 8]

totalWeight = 5时,bestValues[6][9](只有蓝色部分)数组的产生过程:

详解一下红色的34是怎么得到的:此时背包重量为4,只能选择前3个物品,且当前物品重量为3,小于背包的承重4,bestValues[3][4] = max{  bestValues[2][4]   ,  24+bestValues[2][1]  } , 比较的是不放编号3的物品时最大value和放编号3的物品时的最大value。

关于动态规划就讲到这里啦,我觉得最难的地方在于怎么把问题分阶段的考虑,以及推导出递推式子。

如有错误,欢迎指正。


 

作者:jy的blog