域名做网站名,职业培训机构需要什么资质,wordpress网站搭建教程视频,医疗网站建设 飞沐概述
淘宝的 “双十一” 购物节有各种促销活动#xff0c;比如 “满 200 元减 50元”。假设你女朋友购物车中有 n 个#xff08;n 100#xff09;想买的商品#xff0c;它希望从里面选几个#xff0c;在凑够满减条件的前提下#xff0c;让选出来的商品价格总和最长…概述
淘宝的 “双十一” 购物节有各种促销活动比如 “满 200 元减 50元”。假设你女朋友购物车中有 n 个n 100想买的商品它希望从里面选几个在凑够满减条件的前提下让选出来的商品价格总和最长成都接近满减条件200 元这样就可以极大限度地 “薅羊毛”。作为程序员的你能不能编个代码来帮她搞定
要想高效地解决这个问题就要用到本章讲的动态规划Dynamic Programming。 动态规划学习线路
动态规划比较适合用来求解最优问题比如求最大值、最小值等等。它可以非常显著地降低时间复杂度提高代码的执行效率。不过它也是出了名的难学。它的主要学习难点跟递归类似那就是求解问题的过程不太符合人类常规的思维方式。对于新手来说想要入门确实不容易。不过等你掌握了之后你会发现实际上并没有想象中那么难。
为了让你更容易理解动态规划我分了三章进行讲解。这三章分别是初始动态规划、动态规划理论、动态规划实战。
第一章我会通过两个非常经典的动态规划问题模型向你展示我们为什么需要动态规划以及动态规划解题方法是如何演化出来的。实际上你只要掌握了这两个例子的解决思路对于其他很多动态规划问题你都可以套用类似的思路来解决。
第二章我会总结动态规划适合解决的问题的特征以及动态规划解题思路。此外还会将贪心、分治、回溯、动态规划这四种算法思想放在一起对比分析它们各种的特点以及适用的场景。
第三章我会教你应用第二节讲的动态规划理论知识实战解决三个非常经典的动态规划问题加深你对理论的理解。弄懂了这三章中的例子对于动态规划这个知识点你就算是入门了。
0-1 背包问题
再讲贪心算法、回溯算法时多次讲到背包问题。本章依旧拿这个问题来举例。
对于一组不同重量、不可分割的物品我们需要选择一些装入背包在满足背包最大重量限制的前提下背包中物品总重量的最大值是多少
关于这个问题上篇文章讲了回溯的解决方法也就是穷举搜索所有可能得装法然后找出满足条件的最大值。不过回溯算法的复杂度比较高是指数级别。有没有什么规律可以有效降低时间复杂度呢我们一起来看看。 // 回溯算法实现private int maxW Integer.MIN_VALUE; // 结果放到 maxW 中private int[] weight {2,2,4,6,3}; // 物品重量private int n 5; // 物品个数private int w 9; // 背包承受的最大重量public void f(int i, int cw) { // 调用f(0,0)if (cw w || i n) { // cw w表示装满了in表示物品都考察完了if (cw maxW) maxW cw;return;}f(i1, cw); // 选择不装第i个物品if (cw weight[i] w) {f(i1, cw weight[i]); // 选择装第i个物品}}规律是不是不好找那我们就举个例子、画个图看看。我们假设背包的最大承重是 9。我们有 5 个不同的物品每个物品的重量分别是 2,2,4,6,3。如果我们把这个例子的回溯求解过程用递归树画出来就是下面这个样子 递归树种的每个结点表示一种状态我们用 (i, cw) 来表示。其中i 表示将要决策第几个物品是否装入背包cw 表示当前背包中物品的总重量。比如(2, 2) 表示我们将要决策第 2 个物品是否装入背包在决策前背包中的总总量是 2。
从递归树中你应该会发现有些子问题的求解是重复的比如 f(2, 2) 和 f(3,4) 都被重复计算了两次。我们可以借助递归那一节将的 “备忘录” 的解决方式记录已经计算好的 f(i,cw)当再次计算到重复的 f(i,cw) 时可以直接从备忘录中取出来用就不用再递归计算了这样就可以比避免冗余计算。 // 回溯算法实现private int maxW Integer.MIN_VALUE; // 结果放到 maxW 中private int[] weight {2,2,4,6,3}; // 物品重量private int n 5; // 物品个数private int w 9; // 背包承受的最大重量private boolean[][] mem new boolean[5][10]; //备忘录默认为falsepublic void f(int i, int cw) { // 调用f(0,0)if (cw w || i n) { // cw w表示装满了in表示物品都考察完了if (cw maxW) maxW cw;return;}if (mem[i][cw]) return; // 重复状态mem[i][cw] true;f(i1, cw); // 选择不装第i个物品if (cw weight[i] w) {f(i1, cw weight[i]); // 选择装第i个物品}}这种解决方法非常好。实际上它已经跟动态规划的执行效率基本上没有差别。但是多一种方法就多一种解决思路我们现在来看看动态规划是怎么做的。
我们把整个求解过程分为 n 个阶段每个阶段会决策一个物品是否放到背包中。每个物品的决策放入或不放入背包完之后背包中的重量会有多种情况也就是说会达到多种不同的状态对应到递归树中就是有很多不同的节点。
我们把每一层重复的状态节点合并只记录不同的状态然后基于上一层的状态集合来推导下一层的状态集合。我们可以通过合并每一层的重复状态这样就保证每一层不同状态的个数斗不过超过 w 个w 表示背包的承载重量也就是例子中的 9。于是我们就成功避免了每层状态个数的指数级增长。
我们用一个二维数组 states[n][w1]来记录每层可以达到的不同状态。
第 0 个下标从 0 开始编号物品的重量是 2要么装入背包要么不装入背包决策完之后会对应背包的两种状态背包中物品的总重量是 0 或者 2。我们用 state[0][0]true 和 state[0][2]true 来表示这两种状态。
第 1 个物品的重量是 2基于之前的背包状态在这个物品决策完之后不同的状态有 3 个背包中物品总重量分别是 0(00)2(02 or 20)4(22)。我们用 state[1][0]true, state[1][2]true, state[1][4]true 来表示这三种状态。
依次类推直到考察完所有的物品后整个 states 状态数组就计算好了。我把整个计算的过程画了出来你可以看看。图中 0 表示 false1 表示 true。我们只需要在最后一层找一个职位 true 的最近接 w这里是 9的值就是背包中物品总重量的最大值。 文字描述可能不够清楚。我把上面的过程翻译成代码你可以结合着一款看下。 // weight物品重量n物品个数w背包重量public int knapsack(int[] weight, int n, int w) {boolean[][] states new boolean[n][w1]; // 默认值faslestates[0][0] true; // 第一行的数据要特殊处理可以利用哨兵优化if (weight[0] w) {states[0][weight[0]] true;}for (int i 1; i n; i) { // 动态规划状态转移for (int j 0; j w; j) { // 不把第i个物品放入背包if (states[i-1][j] true) states[i][j] true;}for (int j 0; j w - weight[i]; j) { // 把第i个物品放入背包if (states[i-1][j] true) states[i][jweight[i]] true;}}for (int i w; i 0; i--) { // 输出结果if (states[n-1][i] true) return i;}return 0;}实际上这就是一种用动态规划解决问题的思路。我们把问题分解为多个阶段每个阶段对应一个决策。我们记录每一个阶段可达的状态集合去掉重复的然后通过当前阶段的状态集合来推导下一阶段的状态集合动态地往前推进。这也是动态规划这个名字的由来你可以自己体会一下是不是还挺形象的
前面我们讲到用回溯算法解决这个问题的时间复杂度是 O ( 2 n ) O(2^n) O(2n)是指数级的。那动态规划解决方案的时间复杂度是多少呢
这个代码的时间复杂度非常好分析耗时最多的部分就是代码中的两层 for 循环所以时间复杂度是 O ( n ∗ w ) O(n*w) O(n∗w)。n 表示物品个数w 表示背包可以承受的总重量。
从理论上讲指数级的时间复杂度肯定要比 O ( n ∗ w ) O(n*w) O(n∗w) 高很多。为了让你有更加深刻的感受我来举个例子给你比较一下。
我们假设有 10000 个物品重量分布在 1 到 15000 之间背包可以承载的总重量是 30000。如果我们用回溯法解决用具体的数值表示出时间复杂度是 2 10000 2^{10000} 210000这是一个相当大的数字。如果我们用动态规划解决用具体的数值表示出时间复杂度就是 10000*30000。虽然看起来也很大但是和 2 10000 2^{10000} 210000 比起来要小太多。
尽管动态规划的执行效率比较高但是就刚刚的代码来说我们需要额外申请一个 n 乘以 m1 的二维数组对空间的消耗比较多。所以有时候我们会说动态规划是一种空间换时间的解决思路。你可能要问了有什么办法可以降低空间消耗吗
实际上我们只需要一个大小为 w1 的一维数组就可以解决这个问题。动态规划状态转移的过程都可以基于一个一维数组来操作。具体的代码实现如下所示你可以仔细看下。 public int knapsack2(int[] weight, int n, int w) {boolean[] states new boolean[w1]; // 默认值faslestates[0] true; // 第一行的数据要特殊处理可以利用哨兵优化if (weight[0] w) {states[weight[0]] true;}for (int i 1; i n; i) { // 动态规划状态转移// 不把第i个物品放入背包与i-1的结果一致所以不用再处理for (int j w - weight[i]; j 0; j--) { // 把第i个物品放入背包if (states[j] true) states[jweight[i]] true;}}for (int j w; j 0; j--) { // 输出结果if (states[j] true) return j;}return 0;}我强调一下代码中的第 9 行j 需要从大到小来处理。如果我们按照 j 从小到大处理的话会出现 for 循环重复计算的问题。
0-1 背包问题升级版
我们继续升级难度。我改造了一下刚刚的背包问题。你看下这个问题又该如何用动态规划解决呢
刚刚讲的背包问题只涉及背包重量和物品重量。我们现在引入物品价值这一变量。对于一组不同重量、不同价值、不可分割的物品我们选择将某些物品放入背包在满足背包最大重量限制的前提下背包中装入物品的总结之最大是多少呢
这个问题依旧可以用回溯算法来解决。这个问题并不复杂所以具体的实现思路就不用文字描述了直接给你看代码。 // 回溯算法实现private int maxV Integer.MIN_VALUE; // 结果放到 maxW 中private int[] weight {2,2,4,6,3}; // 物品重量private int[] value {3,4,8,9,6}; // 物品价值private int n 5; // 物品个数private int w 9; // 背包承受的最大重量public void f(int i, int cw, int cv) { // 调用f(0,0,0)if (cw w || i n) { // cw w表示装满了in表示物品都考察完了if (cw maxV) maxV cw;return;}f(i1, cw, cv); // 选择不装第i个物品if (cw weight[i] w) {f(i1, cw weight[i], cv value[i]); // 选择装第i个物品}}针对上面的代码我们还是照例画出递归树。在递归树中每个节点表示一个状态。现在我们需要 3 个变量 (i,cw,cv) 来表示一个状态。其中i 表示即将要决策的第 i 个物品是否装入背包cw 表示当前背包中物品的总重量cv 表示当前背包中物品的总价值。 我们发现在递归树中有几个节点 i 和 cw 是相同的比如 f(2,2,4) 和 f(2,2,3)。在背包中物品总重量是一样的情况下f(2,2,4) 这种状态对应的物品总价值更大我们可以舍弃 f(2,2,3) 这种状态只需要沿着 f(2,2,4) 这条决策路线继续往下决策就可以。
也就是说对于 (i,cw) 相同的不同状态我们只需要保留 cv 值最大的那个继续递归处理其他状态不予考虑。
思路说完了但是代码如何实现呢如果用回溯算法这个问题就没法再用 “备忘录” 解决了。所以我们就需要换种思路看看动态规划是不是更容易地解决这个问题
我们还是把整个求解过程分为 n 个阶段每个阶段会决策一个物品是否放到背包中。每个阶段决策完之后背包中的物品的总重量以及总价值会有多种情况也就会达到多种不同的状态。
我们用一个二维数组 states[n][w1]来记录每层可达到的不同状态。不过这里数组存储的值不再试 boolean而是当前状态对应地最大总价值。我们把每一层中 (i,cw) 重复的状态节点合并只记录 cv 值最大的那个状态然后基于这些状态来推导下一层的状态。
我们把这个动态规划的过程翻译成代码就是下面这个样子。 // weight物品重量value物品价值n物品个数w背包重量public int knapsack3(int[] weight, int[] value, int n, int w) {int[][] states new int[n][w1];for (int i 1; i n; i) { // 初始化statesfor (int j 0; j w; j) {states[i][j] -1;}}states[0][0] 0; // 第一行的数据要特殊处理可以利用哨兵优化if (weight[0] w) {states[0][weight[0]] value[0];}for (int i 1; i n; i) { // 动态规划状态转移for (int j 0; j w; j) { // 不把第i个物品放入背包if (states[i-1][j] 0) states[i][j] states[i-1][j];}for (int j 0; j w - weight[i]; j) { // 把第i个物品放入背包if (states[i-1][j] 0) {int v states[i-1][j] value[i];if (v states[i][j weight[i]]) {states[i][j weight[i]] v;}}}}// 找出最大值int maxValue -1;for (int j w; j 0; j--) { // 输出结果if (states[n-1][j] maxValue) maxValue states[n-1][j];}return maxValue;}关于这个问题的时间、空间复杂度的分析跟上一个例子大同小异所以就不赘述了。我直接给出答案时间复杂度是 O ( n ∗ w ) O(n*w) O(n∗w)空间复杂度也是 O ( n ∗ w ) O(n*w) O(n∗w)。跟上一个例子类似空间复杂度也是可以优化的你可以自己写一下。
如何巧妙解决“双十一”购物时的凑单问题
对于这个问题你当然可以利用回溯算法穷举所有的排列组合看大于等于 200 并且最接近 200 的组合是哪一个但是这样效率太低了点时间复杂度非常高是指数级的。当 n 很大时可能 “双十一” 已经结束了你的代码还没有运行处结果这显然会让你在女朋友心中的形象大大减分。
实际上它跟第一个例子中讲的 0-1 背包问题很像只不过是把 “重量” 换成了价格。购物车中有 n 个商品。我们针对每个商品都决策是否否买。每次决策之后对应不同的状态集合。我们还是用一个二维数组 states[n][x]来记录每次决策之后所有可达的状态。不过这里的 x 值是多少呢
0-1 背包问题中我们找的是小于等于 w 的最大值x 就是背包的最大承载重量 w1。对于这个问题来说我们要找的是大于等于 200满减条件的值中最小的所以就不能设置 200 加 1了。就这个实际的问题而言如果要购买的物品的总价格超过 200 太多比如 1000那这个羊毛 “薅” 得就没有太大意义了。所以我们可以限定 x 值为 1001。
不过这个问题不仅要求大于等于 200 的总价格中的最小的我们还要找出这个最小总价对应都该买哪些商品。实际上我们可以利用 states 数组倒推出这个被选择的商品序列。我先把代码写出来待会再照着代码给你解释。 // items:商品价格n商品个数w满减条件比如200public void double11advance(int[] items, int n, int w) {boolean[][] states new boolean[n][3*w1]; // 超过3被就没有薅羊毛的价值了states[0][0] true; // 第一行的数据要特殊处理可以利用哨兵优化if (items[0] 3*w) {states[0][items[0]] true;}for (int i 1; i n; i) { // 动态规划状态转移for (int j 0; j 3*w; j) { // 不买第i个商品if (states[i-1][j] true) states[i][j] states[i-1][j];}for (int j 3*w - items[i]; j 0; j--) { // 买第i个商品if (states[i-1][j] true) states[i][jitems[i]] true;}}int j;for (j w; j 3*w1; j) {if (states[n-1][j] true) break; // 输出结果大于等于w的最小值}if (j 3*w1) return; // 没有可行解for (int i n-1; i 0; i--) {if (j - items[i] 0 states[i-1][j-items[i]] true) {System.out.print(items[i] ); // 购买这个商品j j - items[i];} // else 没有购买这个商品j不变}if (j ! 0) System.out.print(items[0]);}代码的前半部分跟 0-1 背包问题没有什么不同我们着重看下后半部分看它是如何打印出选择购买哪些商品的。
状态 (i,j) 只有可能从 (i-1,j) 或者 (i-1, j-items[i]) 这两个状态推到过来。所以我们就检查这两个状态是否是可达的也就是 states[i-1][j] 或 states[i-1][j-items[i]] 是否为 true。
如果 states[i-1][j] 可达就说明我们没有购买第 i 个上篇如果 states[i-1][j-items[i]] 可达那就说明我们选择购买了第 i 个商品。我们从中选择一个可达的状态如果两个都可达就随意选择一个然后继续迭代地考察其他商品是否有选择购买。
小结
动态规划的第一章到此就讲完了。内容比较多你可能要多花一点时间来消化。
本章的内容不涉及动态规划的理论我通过两个例子给你展示了动态规划是如何解决问题的并且一点一点详细给你讲解了动态规划解决问题的思路。这两个例子都是非常经典的动态规划问题只要你真正搞懂了这两个问题基本上动态规划就已经入门一半了。所以你要多花点时间真正弄懂这两个问题。
从例子中你应该能发现大部分动态规划能解决的问题都可以通过回溯法来解决只不过回溯算法解决起来比较低效时间复杂度是指数级的。动态规划算法在执行效率方面要高很多。尽管执行效率提高了但是动态规划的空间复杂度也提高了所以很多时候我们会说动态规划是一种空间换时间的算法思想。
前面也说了本章的内容不涉及理论知识。这两个例子的分析过程我并没有涉及任何高深的理论方面的东西。而且我个人觉得贪心、分治、回溯、动态规划这四个算法有关的理论知识大部分都是 “后验性” 的也就是说在解决问题的过程中我们往往是先想到如何用某个算法思想解决问题然后才用算法理论知识去验证这个算法思想解决问题的正确性。所以你大可不必过于急于寻求动态规划的理论知识。
