关于算法:陪女朋友逛街引起的算法问题

女朋友去北京路逛街的时候看到了很多好吃的，特地想吃，然而咱豪气，女朋友想吃啥就买啥

“背包问题”

遇到了一个问题，女朋友的 胃口无限，咱该如何解决呢

五大算法

1. 分治法

我：这么多美食，咱能吃的也不多，不过能够分成 3 大类：主食、小吃、饮料

女朋友：主食的话，有猪脚卤粉、麻辣烫、凉拌 … 算了，咱们还是吃螺蛳粉吧~

女朋友：小吃的话，有周黑鸭、串串、兔头 … 算了，咱们还是吃臭豆腐吧~

女朋友：饮料的话，有酸奶、西瓜汁、金桔柠檬 … 还是喝菠萝啤吧~

我提出了将想吃的分成了 3 大类，等于将“吃什么”这个大问题分成了“怎么抉择主食、小吃、饮料”3 个小问题

分治法（分而治之）：待解决简单的问题可能简化为几个若干个小规模雷同的问题，而后逐渐划分，达到易于解决的水平。

女朋友的 3 次答复都是反复思考怎么在同品种美食里抉择本人最喜爱的

递归：间接或者间接一直重复调用本身来达到解决问题的办法，要求原始问题能够分解成雷同问题的子问题

2. 贪婪算法

女朋友不批准我的上一个说法，就是想吃

我：真拿你没方法，据我对宝宝的理解，我给你按你最喜爱吃的给你排序：小龙虾 > 牛蛙 > 臭豆腐 > 炸串 > 蕨根粉 > 凤爪 …

女朋友：那咱们先吃小龙虾~

（一个小时后）

女朋友：小龙虾吃得好饱啊，牛蛙和臭豆腐我曾经吃不下了，可是我还能吃炸串，冲冲冲~

（半小时后）

女朋友：好饱啊，其它都吃不下了，只能喝点货色了，有奶茶、水果茶 … 那咱们买杯西瓜汁吧~

女朋友在吃完最爱吃的货色后，再依据剩下的胃口抉择最喜爱的

贪婪算法：就问题而言，抉择当下最好的抉择，而不从整体最优思考，通过部分最优心愿导致全局最优

3. 动静布局

我：既然不晓得该吃啥，咱把问题简化一下，假设“6 成饿”=“4 成饱”，“7 成饿”=“3 成饱”，如果当初你只有 0 成饿，也就是十分饱，你会吃什么？

女朋友：0 成饿 当然是什么都吃不下了

我：如果只有 1 成饿，你会吃什么？

女朋友：那我只能吃个甜筒 ~

我：如果只有 2 成饿，你会吃什么？

女朋友：尽管能吃的有很多，像 奶茶 / 柠檬茶 等等，然而我还是打算喝杯 酸奶 ~

我：是不是也能够吃 2 个 甜筒 ~ 那如果只有 3 成饿，你会吃什么？

女朋友：能吃的就多了~ 有 凤爪 / 臭豆腐 / 炸串 ~ 但我还是最喜爱 臭豆腐 ~

我：其实还能够吃 甜筒 + 酸奶~ 如果只有 4 成饿，你会吃什么？

女朋友：牛蛙 / 火锅 / 炸串 等等 但我最喜爱牛蛙~

我：列出一个表格

我：思考到反复的美食不纳入思考范畴，进行表格优化

女朋友：我感觉再加上思考价格的因素~ 就像 3 成饱的时候，臭豆腐 比 甜筒 + 酸奶 要划算；4 成饱的时候，牛蛙 比 臭豆腐 + 甜筒 要划算，再次优化表格

我：那咱们以此类推，补充残余表格

咱们先把问题拆分至不可再拆分的问题再倒推回去

动静布局：组合子问题的解来解决原问题的解

4. 回溯算法

女朋友：我也拿不定主见

我：这里整个商业区那么多美食，还盘根错节那么多的分岔口，不如咱们先沿着这条道始终往下走，碰到想吃的咱就买

女朋友：好啊，可是这条道走到止境了也没有吃饱怎么办

我：咱们就回到最近的分岔口，走到另一条道持续看嘛~

咱们先抉择某条路走到底，直到走到止境再返回到路口，抉择另一条道持续走上来

（尝试某一特定路线，如果没有后续也解决方案则 回溯 到上一步）

回溯算法：深度优先策略的典型利用，回溯算法就是沿着一条路向下走，如果此路不同了，则回溯到上一个分岔路，在选一条路走，始终这样递归上来，直到遍历万所有的门路

5. 分支界线法

我：这里也太大了，不如咱们就抉择这条街的美食，其它中央的咱们当前再尝

女朋友很欢快地许可了~

分支界线法：在满足约束条件的解中找出使某一指标函数值达到极大或极小的解，即在某种意义下的最优解

其它算法

6. 暴力法

思考到最近涨薪，我决定豪气一把，所有女朋友爱吃的统统买了，而后就吃一口，剩下的全扔了，尽管啥都吃上了，可是造成的节约十分大（不举荐）

最初，我和女朋友都吃饱了回家了~

大家也学会了算法~ 完结撒花