【陪女朋友逛街】引起的算法问题
女朋友去北京路逛街的时候看到了很多好吃的，特别想吃，但是咱豪气，女朋友想吃啥就买啥
文章图片
“背包问题”
遇到了一个问题，女朋友的胃口有限，咱该如何处理呢
文章图片
五大算法
1. 分治法
我：这么多美食，咱能吃的也不多，不过可以分成3大类：主食、小吃、饮料
女朋友：主食的话，有猪脚卤粉、麻辣烫、凉拌... 算了，我们还是吃螺蛳粉吧~
文章图片
女朋友：小吃的话，有周黑鸭、串串、兔头... 算了，我们还是吃臭豆腐吧~
文章图片
女朋友：饮料的话，有酸奶、西瓜汁、金桔柠檬... 还是喝菠萝啤吧~
文章图片
我提出了将想吃的分成了3大类，等于将 “ 吃什么 ” 这个大问题分成了 “ 怎么选择主食、小吃、饮料 ” 3个小问题
分治法（分而治之）：待解决复杂的问题能够简化为几个若干个小规模相同的问题，然后逐步划分，达到易于解决的程度。女朋友的3次回答都是重复思考怎么在同种类美食里选择自己最喜欢的
递归：直接或者间接不断反复调用自身来达到解决问题的方法，要求原始问题可以分解成相同问题的子问题2. 贪心算法
女朋友不同意我的上一个说法，就是想吃
文章图片
我：真拿你没办法，据我对宝宝的了解，我给你按你最喜欢吃的给你排序：小龙虾 > 牛蛙 > 臭豆腐 > 炸串 > 蕨根粉 > 凤爪 ...
女朋友：那我们先吃小龙虾~
文章图片
（一个小时后）
女朋友：小龙虾吃得好饱啊，牛蛙和臭豆腐我已经吃不下了，可是我还能吃炸串，冲冲冲~
文章图片
（半小时后）
女朋友：好饱啊，其它都吃不下了，只能喝点东西了，有奶茶、水果茶... 那我们买杯西瓜汁吧~
文章图片
女朋友在吃完最爱吃的东西后，再根据剩下的胃口选择最喜欢的
贪心算法：就问题而言，选择当下最好的选择，而不从整体最优考虑，通过局部最优希望导致全局最优3. 动态规划
我：既然不知道该吃啥，咱把问题简化一下，假定 “6成饿” = “4成饱” ，“7成饿” = “3成饱” ，如果现在你只有 0成饿，也就是非常饱，你会吃什么？
女朋友：0成饿 当然是什么都吃不下了
文章图片
我：如果只有 1成饿，你会吃什么？
女朋友：那我只能吃个甜筒 ~
文章图片
我：如果只有 2成饿，你会吃什么？
女朋友：虽然能吃的有很多，像 奶茶 / 柠檬茶 等等，但是我还是打算喝杯 酸奶 ~
文章图片
我：是不是也可以吃2个 甜筒 ~那如果只有 3成饿，你会吃什么？
女朋友：能吃的就多了~ 有 凤爪 / 臭豆腐 / 炸串 ~但我还是最喜欢 臭豆腐 ~
文章图片
我：其实还可以吃 甜筒 + 酸奶~如果只有 4成饿，你会吃什么？
女朋友：牛蛙 / 火锅 / 炸串 等等 但我最喜欢牛蛙~
文章图片
我：列出一个表格
| 饿度 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 食物 | 无 | 甜筒 | 酸奶 2个甜筒 |
臭豆腐 甜筒+酸奶 3个甜筒 |
牛蛙 臭豆腐+甜筒 2杯酸奶 4个甜筒 |
| 饿度 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 食物 | 甜筒 | 酸奶 | 臭豆腐 甜筒+酸奶 |
牛蛙 臭豆腐+甜筒 |
| 饿度 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 食物 | 甜筒 | 酸奶 | 臭豆腐 | 牛蛙 |
| 饿度 | 1 | 2 | 3 | 4 | 5 | 6 | ... | 10 |
|---|---|---|---|---|---|---|---|---|
| 食物 | 甜筒 | 酸奶 | 臭豆腐 | 牛蛙 | 牛蛙+甜筒 臭豆腐+酸奶 |
牛蛙+酸奶 臭豆腐+酸奶+甜筒 |
... | f(9)+f(1) f(8)+f(2) ... |
我们先把问题拆分至不可再拆分的问题再倒推回去
动态规划：组合子问题的解来解决原问题的解4. 回溯算法
女朋友：我也拿不定主意
我：这里整个商业区那么多美食，还错综复杂那么多的分岔口，不如我们先沿着这条道一直往下走，碰到想吃的咱就买
女朋友：好啊，可是这条道走到尽头了也没有吃饱怎么办
我：我们就回到最近的分岔口，走到另一条道继续看嘛~
文章图片
我们先选择某条路走到底，直到走到尽头再返回到路口，选择另一条道继续走下去
（尝试某一特定路线，如果没有后续也解决方案则 回溯 到上一步）
回溯算法：深度优先策略的典型应用，回溯算法就是沿着一条路向下走，如果此路不同了，则回溯到上一个分岔路，在选一条路走，一直这样递归下去，直到遍历万所有的路径5. 分支界限法
我：这里也太大了，不如我们就选择这条街的美食，其它地方的我们以后再尝
女朋友很愉快地答应了~
文章图片
分支界限法：在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解其它算法 6. 暴力法
考虑到最近涨薪，我决定豪气一把，所有女朋友爱吃的通通买了，然后就吃一口，剩下的全扔了，虽然啥都吃上了，可是造成的浪费非常大（不推荐）
文章图片
最后，我和女朋友都吃饱了回家了~ 【【陪女朋友逛街】引起的算法问题】大家也学会了算法~完结撒花
文章图片
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长