40初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?.pdf
《40初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?.pdf》由会员分享,可在线阅读,更多相关《40初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?.pdf(17页珍藏版)》请在三一文库上搜索。
1、40|初识动态规划:如何巧妙解决“双十一”购物时的凑单问题? file:/F/temp/geektime/数据结构与算法之美/40初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?.html2019/1/15 15:36:28 40|初识动态规划:如何巧妙解决“双十一”购物时的凑单问题? 淘宝的“双十一”购物节有各种促销活动,比如“满200元减50元”。假设你女朋友的购物车中有n个(n100)想买的商品,她希望从里面选几个,在凑够满减条件的 前提下,让选出来的商品价格总和最大程度地接近满减条件(200元),这样就可以极大限度地“薅羊毛”。作为程序员的你,能不能编个代码来帮她搞定呢? 要想高
2、效地解决这个问题,就要用到我们今天讲的动态规划(Dynamic Programming)。 动态规划学习路线 动态规划比较适合用来求解最优问题,比如求最大值、最小值等等。它可以非常显著地降低时间复杂度,提高代码的执行效率。不过,它也是出了名的难学。它 的主要学习难点跟递归类似,那就是,求解问题的过程不太符合人类常规的思维方式。对于新手来说,要想入门确实不容易。不过,等你掌握了之后,你会发 现,实际上并没有想象中那么难。 为了让你更容易理解动态规划,我分了三节给你讲解。这三节分别是,初识动态规划、动态规划理论、动态规划实战。 第一节,我会通过两个非常经典的动态规划问题模型,向你展示我们为什么需要
3、动态规划,以及动态规划解题方法是如何演化出来的。实际上,你只要掌握了这 两个例子的解决思路,对于其他很多动态规划问题,你都可以套用类似的思路来解决。 第二节,我会总结动态规划适合解决的问题的特征,以及动态规划解题思路。除此之外,我还会将贪心、分治、回溯、动态规划这四种算法思想放在一起,对比 分析它们各自的特点以及适用的场景。 第三节,我会教你应用第二节讲的动态规划理论知识,实战解决三个非常经典的动态规划问题,加深你对理论的理解。弄懂了这三节中的例子,对于动态规划这 个知识点,你就算是入门了。 0-1背包问题 我在讲贪心算法、回溯算法的时候,多次讲到背包问题。今天,我们依旧拿这个问题来举例。 对
4、于一组不同重量、不可分割的物品,我们需要选择一些装入背包,在满足背包最大重量限制的前提下,背包中物品总重量的最大值是多少呢? 关于这个问题,我们上一节讲了回溯的解决方法,也就是穷举搜索所有可能的装法,然后找出满足条件的最大值。不过,回溯算法的复杂度比较高,是指数级别 的。那有没有什么规律,可以有效降低时间复杂度呢?我们一起来看看。 / 回溯算法实现。注意:我把输入的变量都定义成了成员变量。 private int maxW = Integer.MIN_VALUE; / 结果放到maxW中 private int weight = 2,2,4,6,3; / 物品重量 private int n
5、= 5; / 物品个数 private int w = 9; / 背包承受的最大重量 public void f(int i, int cw) / 调用f(0, 0) if (cw = w | i = n) / cw=w表示装满了,i=n表示物品都考察完了 if (cw maxW) maxW = cw; return; f(i+1, cw); / 选择不装第i个物品 if (cw + weighti maxW) maxW = cw; return; if (memicw) return; / 重复状态 memicw = true; / 记录(i, cw)这个状态 f(i+1, cw); / 选
6、择不装第i个物品 if (cw + weighti = 0; -i) / 输出结果 if (statesn-1i = true) return i; return 0; 实际上,这就是一种用动态规划解决问题的思路。我们把问题分解为多个阶段,每个阶段对应一个决策。我们记录每一个阶段可达的状态集合(去掉重复的), 然后通过当前阶段的状态集合,来推导下一个阶段的状态集合,动态地往前推进。这也是动态规划这个名字的由来,你可以自己体会一下,是不是还挺形象的? O(2n) 40|初识动态规划:如何巧妙解决“双十一”购物时的凑单问题? file:/F/temp/geektime/数据结构与算法之美/40初识
7、动态规划:如何巧妙解决“双十一”购物时的凑单问题?.html2019/1/15 15:36:28 前面我们讲到,用回溯算法解决这个问题的时间复杂度,是指数级的。那动态规划解决方案的时间复杂度是多少呢?我来分析一下。 这个代码的时间复杂度非常好分析,耗时最多的部分就是代码中的两层for循环,所以时间复杂度是O(n*w)。n表示物品个数,w表示背包可以承载的总重量。 从理论上讲,指数级的时间复杂度肯定要比O(n*w)高很多,但是为了让你有更加深刻的感受,我来举一个例子给你比较一下。 我们假设有10000个物品,重量分布在1到15000之间,背包可以承载的总重量是30000。如果我们用回溯算法解决,
8、用具体的数值表示出时间复杂度,就 是210000,这是一个相当大的一个数字。如果我们用动态规划解决,用具体的数值表示出时间复杂度,就是10000*30000。虽然看起来也很大,但是和210000比 起来,要小太多了。 尽管动态规划的执行效率比较高,但是就刚刚的代码实现来说,我们需要额外申请一个n乘以w+1的二维数组,对空间的消耗比较多。所以,有时候,我们会说, 动态规划是一种空间换时间的解决思路。你可能要问了,有什么办法可以降低空间消耗吗? 实际上,我们只需要一个大小为w+1的一维数组就可以解决这个问题。动态规划状态转移的过程,都可以基于这个一维数组来操作。具体的代码实现我贴在这里, 你可以仔
9、细看下。 public static int knapsack2(int items, int n, int w) boolean states = new booleanw+1; / 默认值false states0 = true; / 第一行的数据要特殊处理,可以利用哨兵优化 statesitems0 = true; for (int i = 1; i = 0; -j) /把第i个物品放入背包 if (statesj=true) statesj+itemsi = true; for (int i = w; i = 0; -i) / 输出结果 if (statesi = true) retu
10、rn i; return 0; 这里我特别强调一下代码中的第6行,j需要从大到小来处理。如果我们按照j从小到大处理的话,会出现for循环重复计算的问题。你可以自己想一想,这里我就不 详细说了。 0-1背包问题升级版 我们继续升级难度。我改造了一下刚刚的背包问题。你看这个问题又该如何用动态规划解决? 我们刚刚讲的背包问题,只涉及背包重量和物品重量。我们现在引入物品价值这一变量。对于一组不同重量、不同价值、不可分割的物品,我们选择将某些物品 装入背包,在满足背包最大重量限制的前提下,背包中可装入物品的总价值最大是多少呢? 这个问题依旧可以用回溯算法来解决。这个问题并不复杂,所以具体的实现思路,我就
11、不用文字描述了,直接给你看代码。 private int maxV = Integer.MIN_VALUE; / 结果放到maxV中 private int items = 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表示装满了,i=n表示物品都考察完了 4
12、0|初识动态规划:如何巧妙解决“双十一”购物时的凑单问题? file:/F/temp/geektime/数据结构与算法之美/40初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?.html2019/1/15 15:36:28 if (cv maxV) maxV = cv; return; f(i+1, cw, cv); / 选择不装第i个物品 if (cw + weighti = 0) statesij = statesi-1j; for (int j = 0; j = 0) int v = statesi-1j + valuei; if (v statesij+weighti) stat
13、esij+weighti = v; / 找出最大值 int maxvalue = -1; for (int j = 0; j maxvalue) maxvalue = statesn-1j; return maxvalue; 关于这个问题的时间、空间复杂度的分析,跟上一个例子大同小异,所以我就不赘述了。我直接给出答案,时间复杂度是O(n*w),空间复杂度也是O(n*w)。跟上 一个例子类似,空间复杂度也是可以优化的,你可以自己写一下。 解答开篇 掌握了今天讲的两个问题之后,你是不是觉得,开篇的问题很简单? 对于这个问题,你当然可以利用回溯算法,穷举所有的排列组合,看大于等于200并且最接近20
14、0的组合是哪一个?但是,这样效率太低了点,时间复杂度非常 高,是指数级的。当n很大的时候,可能“双十一”已经结束了,你的代码还没有运行出结果,这显然会让你在女朋友心中的形象大大减分。 实际上,它跟第一个例子中讲的0-1背包问题很像,只不过是把“重量”换成了“价格”而已。购物车中有n个商品。我们针对每个商品都决策是否购买。每次决策之 后,对应不同的状态集合。我们还是用一个二维数组statesnx,来记录每次决策之后所有可达的状态。不过,这里的x值是多少呢? 40|初识动态规划:如何巧妙解决“双十一”购物时的凑单问题? file:/F/temp/geektime/数据结构与算法之美/40初识动态规
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 40 初识 动态 规划 如何 巧妙 解决 十一 购物 问题
链接地址:https://www.31doc.com/p-5529995.html