内容简介:都说程序员是直男,聊天聊不过三句,看下边这位朋友求助小鹿,抱怨说,学习数据结构那么难,除了优化程序算法,其他的啥都不能干,学它干啥,哎,撩个妹子都撩不到。说真的,我都嫌弃他,哈哈,嫌弃归嫌弃,我还想教给你撩妹的正确方式的,该说不说的,为了能让这位朋友可以撩上妹子,小鹿耗时假期三天时光,出了这篇文章,希望帮助各位宅男们脱单。快过年了,很多吃货都安奈不住了,也包括爱吃零食的小鹿。天猫超市也很多“满减活动”。我想很多程序员和小鹿一样,会在天猫超市有“满减活动”的时候才会买一大些零食,一次性吃个够。
都说 程序员 是直男,聊天聊不过三句,看下边这位朋友求助小鹿,抱怨说,学习数据结构那么难,除了优化程序算法,其他的啥都不能干,学它干啥,哎,撩个妹子都撩不到。
说真的,我都嫌弃他,哈哈,嫌弃归嫌弃,我还想教给你撩妹的正确方式的,该说不说的,为了能让这位朋友可以撩上妹子,小鹿耗时假期三天时光,出了这篇文章,希望帮助各位宅男们脱单。
故事背景
快过年了,很多吃货都安奈不住了,也包括爱吃零食的小鹿。天猫超市也很多“满减活动”。我想很多程序员和小鹿一样,会在天猫超市有“满减活动”的时候才会买一大些零食,一次性吃个够。
那么机会来了,你是个吃货,很多小姐姐也是吃货,何不借此机撩一撩呢?
这怎么撩?凭着你学了数据结构与算法嘛?凭着你是做底层架构的?凭着你会....
这点小事,包在小鹿身上了,下面就给你来个用数据结构与算法实战撩小姐姐,让小姐姐对你的满意度从 0 飙升到 100。
开始搭讪
很多女生说程序员都是直男,没错,我也承认我也是其中一位。
直男是程序员的通病,但是程序员这个职业也赋予了我们随机应变能力呀,懂得自救才行(很多宅男们就败在这了)。
你不仔细想想,作为一个非程序员的妹子,谁喜欢跟你闲着没事讨论这自己不懂的东西。
帮小姐姐解决问题
这个时候,该你展现真正的技术了,可不要搞砸了,不认你的印象又被小姐姐大大降低。
那么问题来了,怎么选择购物车中的零食才能满足尽最大可能凑到“满减活动”呢?
1、动态规划
我们就会用到动态规划去计算,动态规划在数据结构与算法中属于重点也是难点,也会涉及到递归,这部分也是基础中最难的。之前很多读反馈,说分享的教程太基础,所以关于递归基础,这里不讲了,可以公众号后台回复“ 递归 ”,获取基础教程。
首先,我们将复杂问题简单化,假如我们购物车中有 2元、4元、2元、3元、6元的五个价格的零食。假如买够 9 元,我们立减 5 元,我们应该凑满 9 元或者尽可能的大于 9 元并接近 9 元呢?
其实这个问题一眼就能选择出来,但是我们为了将复杂问题解决掉,我们还是用动态规划去解决。
其实这个问题类似于递归,第一个零食买不买有两种选择,一个是买,一个就是不买,第二个、第三个、第四个..... 都有两种选择,这时候我们可以用到递归。
你会说,我们可以用回溯算法把所有可能列出来呀,选择合适的不就好了?记住,我们是程序员,要尽可能的降低时间复杂度,等你全部穷举出来,估计你的小姐姐早就等不及下单了。
这个问题用动态规划怎么解决呢?
我们用(a,b)来表示每个零食是否被选择,a 表示对第 a 个零食是否购买,b 表示已选择购买零食的总价格。
2、用递归树来表示
上边的递归树把所有的情况都列举了出来,就像是我们用到的回溯算法,之所以时间复杂度很高,是因为递归树中有的层次很多重复计算的步骤,如果我们把重复计算的状态只记录一种不就可以减少时间复杂度,提高程序效率了吗?
上边的递归树怎么表示呢?我们可以一个二维数组,tree[a][b],a 表示第 a 个零食是否购买,b 表示已选择购买零食的总价格。
上边递归树我们用代码实现,如下:
/** 2 * 3 * @param prices 各个商品的价格 4 * @param n 商品的个数 5 * @param w 满减条件(满 199-99元) 6 */ 7public static void ShoppingSnacks(int[] prices,int n,int w){ 8 boolean[][] tree = new boolean[n][w+1]; 9 tree[0][0] = true; 10 tree[0][prices[0]] = true; 11 //动态规划 12 for (int i = 1; i < n; i++) { 13 // 不购买当前商品 14 for(int j = 0;j <=w; j++) { 15 //寻找上一个商品决策状态 16 if(tree[i-1][j] == true) { 17 tree[i][j] = true; 18 } 19 } 20 21 // 购买当前商品 22 for(int j = 0;j <=w-prices[i]; j++) { 23 //寻找上一个商品决策状态 24 if(tree[i-1][j] == true) { 25 tree[i][j+prices[i]] = true; 26 } 27 } 28 } 29} 复制代码
上边代码执行完成,所有的情况我们就用二维数组来表示,零食购买的决策状态如下:
◆ 横坐标 代表已经从购物车选择的零食的总价格;
◆ 纵坐标代表 对第 i 个零食进行选择是否购买;
但是上边的代码存在一个问题,求得的最大满足满减条件价格是尽可能小于接近 9 元,我们想要达到的结果是尽可能的达到或超过接近满减条件。怎么做呢? 我们做出以下修改,让满减价格尽可能的大三倍,就是说我们将满足 9 元提升到 27 元,也就是说,在所有零食中,尽可能满足接近 27 元的情况有哪些,我们都能选择出来,接下来我们选择出最接近超过 9 元的情况就可以了。
代码修改如下:
1/** 2 * 3 * @param prices 各个商品的价格 4 * @param n 商品的个数 5 * @param w 满减条件(满 199-99元) 6 */ 7public static void ShoppingSnacks(int[] prices,int n,int w){ 8 //将商品的价格扩展到三倍 9 boolean[][] tree = new boolean[n][3*w+1]; 10 tree[0][0] = true; 11 tree[0][prices[0]] = true; 12 //动态规划 13 for (int i = 1; i < n; i++) { 14 // 不购买当前商品 15 for(int j = 0;j <=3*w; j++) { 16 //寻找上一个商品决策状态 17 if(tree[i-1][j] == true) { 18 tree[i][j] = true; 19 } 20 } 21 22 // 购买当前商品 23 for(int j = 0;j <=3*w-prices[i]; j++) { 24 //寻找上一个商品决策状态 25 if(tree[i-1][j] == true) { 26 tree[i][j+prices[i]] = true; 27 } 28 } 29 } 30} 31 复制代码
那么还有一个问题就是最大可能超过并接近 9 元的情况我们选择出来了,但是怎么把选择的哪些零食列出来呢?
我们利用倒推的方法,这个地方很难理解,可以自己尝试着画图或者根据代码和上边画的二维数组图对应着选择,多看几遍估计就可以看会了,问题不大。
怎么个倒推法呢?假如我们最后一个商品在数组中用 n-1 表示,如果可以通过 tree[n-2][ j - prices[i]],或者 tree[i-1][j] 推到出来,那么这两种状态可以达到,就可以判断当前的这个零食是否购买,如果两种状态都可以达到,我们选择一种就好,以为有这样一种情况就是,到达满减最接近的值可能有很多中情况。
上边介绍完了,那么给小姐姐选择零食尽最大可能的接近满减(199元),我们就可以享受立减 99 元的优惠了!
购物车物品如下:
我们会发现一个问题,小数不能用下标表示,那我们可以将价格以及满减价格同时乘以10,那么就可以计算了。
代码如下:
/** 2 * 【动态规划】 3 * 功能:实现天猫超市 “满减凑单活动” 4 * @author 小鹿 5 * 6 */ 7public class TBShopping { 8 9 /** 10 * 11 * @param prices 各个零食的价格 12 * @param n 零食的个数 13 * @param w 满减条件(满 199-99元) 14 */ 15 public static void ShoppingSnacks(int[] prices,int n,int w){ 16 //将零食的价格扩展到三倍 17 boolean[][] tree = new boolean[n][3*w+1]; 18 tree[0][0] = true; 19 tree[0][prices[0]] = true; 20 21 //动态规划 22 for (int i = 1; i < n; i++) { 23 24 // 不购买当前零食 25 for(int j = 0;j <=3*w; j++) { 26 //寻找上一个零食决策状态 27 if(tree[i-1][j] == true) { 28 tree[i][j] = true; 29 } 30 } 31 32 // 购买当前零食 33 for(int j = 0;j <=3*w-prices[i]; j++) { 34 //寻找上一个商品决策状态 35 if(tree[i-1][j] == true) { 36 tree[i][j+prices[i]] = true; 37 } 38 } 39 } 40 41 //找出需要凑单的零食 42 int j; 43 for(j = w;j < 3*w+1; j++) { 44 //在最后一个零食寻找满足最接近 200 的条件状态 45 if(tree[n-1][j]==true) { 46 System.out.println("满减的最大条件为"+(float)j/10+"元"); 47 break; 48 } 49 } 50 51 //没有可选择零食 52 if(j == -1) { 53 return; 54 } 55 56 // 倒推遍历满足条件的零食 57 for(int i = n-1; i>=1; i--) { 58 //当前账单的总金额大必须于当前零食金额 59 //且上一个商品的决策状态为 true 60 if(j - prices[i]>=0 && tree[i-1][j-prices[i]] == true) { 61 //已购买该零食 62 System.out.println(Snacks[i]+p[i]); 63 j = j - prices[i]; 64 }else { 65 //没有购买该零食 66 67 } 68 } 69 if(j != 0) { 70 System.out.print(Snacks[1]+p[0]); 71 } 72 } 73} 复制代码
运行结果:
当你给小姐姐完成了这项艰巨的选择之后,小姐姐的态度就180 度大转弯了!
本公众号专注于「前端」、「数据结构」互联网技术领域,通俗简单的文字和动漫配图,让你爱上编程。
【Github源码获取方式】:https://github.com/luxiangqiang/Data-Structure-Coding/tree/master/动态规划/满减活动源码
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 「Flask实战」鱼书项目实战一
- 「Flask实战」鱼书项目实战三
- 「Flask实战」鱼书项目实战四
- 「Flask实战」鱼书项目实战六
- RocketMQ实战系列从理论到实战
- 「Flask实战」flask鱼书项目实战二
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Web开发秘方
Brian P. Hogan、Chris Warren、Mike Weber、Chris Johnson、Aaron Godin / 七印部落 / 华中科技大学出版社 / 2013-7-10 / 66.00元
猜猜硅谷的前端工程师怎么折腾JS的?想知道无限下拉的列表怎么做吗?你知道DropBox可以当Web服务器用吗?你知道怎么做出跨平台的幻灯片效果吗?不借助插件,怎样在移动设备上实现动画效果?怎样快速搭建和测试HTML电子邮箱?怎样制作跨PC和移动设备显示的应用界面?怎样利用最新的JavaScript框架(Backbone和Knockout)提高应用的响应速度?怎样有效利用CoffeeScript和S......一起来看看 《Web开发秘方》 这本书的介绍吧!