缘起
额，这篇文章其实是讲动态规划算法的。
很多解释背包问题的文章，上来就给你画表格，然后一通操作猛如虎，得出结论就完事。要么就是给你丢个求和公式，让你套套公式就完事。
这让本学渣非常之不爽。于是我决定结合生活阅历和工作经验，写一篇文章来科普一下，让高中生都能懂动态规划这种行动策略。
问题的描述
维基百科对背包问题是这么描述的：
背包问题（Knapsack problem）是一种组合优化的NP完全问题。 问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。 问题的名称来源于如何选择最合适的物品放置于给定背包中。
简单地说就是小偷入室盗窃要怎么偷走最大价值的物品。
解决此类问题，要先认识问题,搞明白有限的条件，营业收入,营业成本和营业净利润，局部最优解之间的定义和关系。
条件必须是要有限的，不然背包问题没有意义。这是一个非常简单的道理，如果你有一张无限额度并且不需要你还款的信用卡，那你还需要想什么呢，随便刷就完事了。
- 营业收入 = 营业成本+ 净利润；
有限的条件制约了局部最优解，营业净利润和最终的营业收入；
在背包问题中，我对有限的条件，营业收入,营业成本，营业净利润，局部最优解是这样定义的（不考虑法律风险）：
- 有限的条件：背包的容量
- 营业收入： 物品的销赃收入（物品内在价值）
- 营业成本： 物品的重量（背包只能容纳有限重量的的物品）
- 营业净利润：扣除掉成本之后的销赃收入（营业收入-营业成本)
- 局部最优解：背包赃物+1
积极策略：合纵连横
这里以春秋战国作为故事背景。
- 有限的条件：有限的本国人民和国家财政
- 营业收入：侵略获得的领土和领土上面的资源
- 营业成本：维持国家稳定的费用（军费+政府运营费用）
- 营业净利润：本国财政收入
- 局部最优解：合并他国
合纵连横其实也不太准确。我更喜欢“合纵连横”和“高筑墙，广积粮，缓称王”这两种说法的结合体——星星之火，可以燎原。也就是对内团结一致，养精蓄锐，借助盟友的力量拉起交易杠杆，获得更大的收益。
最近在看1983年周润发和赵雅芝主演的《上海滩》，发哥饰演的许文强就非常的经典。他不忘初心，牢记使命。经历过大起大落之后，依然能够坦然面对生活。这是一种真正的英雄主义。他的所作所为，正是完美贯彻了“星星之火，可以燎原”这种战略思想。
消极策略：渣男/绿茶婊（简称渣）
- 有限的条件：渣的青春年华
- 营业收入：舔狗列表
- 营业成本：渣的时间和肉体
- 营业净利润：所有舔狗付出的总和
- 局部最优解：单一舔狗的付出（情感，时间，金钱）
由渣和舔狗的属性得出以下推论：
- 渣维护着一个舔狗集群，这个集群里面得包含各式价值不一的舔狗
- 渣的舔狗都有这样一个特点：求之不得,寤寐思服。出钱出力，在所不惜。
- 越会舔的狗价值越高
渣的最终策略：按照“成本制约净利润”的前提，为了实现最大的净利润，渣会在舔狗之中不断周旋，但不会在每个舔狗身上浪费太多的时间精力金钱。就算掏钱，渣也对投资收益有绝对的把握，一旦投资收益不满意，立刻撤资。
为啥说这种策略消极呢？因为感情交往理应谋求双赢的结局（双方幸福快乐在一起），但是渣们回避了自身的权利和义务，只求榨干对方，实际上是一种忽略风险，为了短期收益而放弃长远收益的愚蠢。不过，也许在他们看来，正常人才是愚蠢的，付出了那么多，却一无所获，远不如他们收割别人来得直截了当。
算法策略：有限财政预算下求共享带宽最优解
这是我最近遇到的一个工作上的问题：在预算有限的情况下利用动态规划，平衡共享带宽里面的EIP。
说人话就是:
- 流量低峰时把EIP纳入共享带宽,节约流量费用;
- 带宽高峰时让EIP移出共享带宽,提高带宽利用率.
分治的逻辑
问题分为扩容和缩容的逻辑
有限的条件：财政预算，等价于带宽营业收入： 略营业成本：共享带宽的保底费用 + EIP产生的带宽费用
以上三点的逻辑都是一致的,差别在于营业净利润和局部最优解的定义。
扩容的逻辑：
- 营业净利润：EIP带宽的负值（带宽越少越好）
- 局部最优解：共享带宽EIP+1(纳入了共享带宽，所以EIP不需要额外计费)
缩容的逻辑：
- 营业净利润：EIP带宽（带宽越多越好，让他大于保底带宽）
- 局部最优解：共享带宽EIP-1 （带宽超过可接受范围，移除掉，让他按流量计费）
统合的逻辑
2020-03-11的时候我发现,我把这个问题过度复杂化了，所以我又把缩容和扩容的逻辑统合了起来。
这个逻辑就是：每次都取当前 region 下的所有EIP，然后根据带宽情况动态增减。有剩余带宽时，从上一行中取出符合剩余带宽要求的最大值。
数组的一维用带宽表示。
二维用当前 region 下所有 EIP 去表示。
数组的内容为带宽值（价值）
流量低谷需要扩容
流量低谷需要扩容的时候，一维的带宽起点=最小带宽-当前带宽；
举个例子，最小带宽=45（Mbps），当前带宽=5(Mbps),起点就是45-5=40
| 0 | 40 | 41 | 42 |
|---|---|---|---|
| 21 | 21 | 21 | 21 |
| 20 | 21 | 41 | 41 |
| 31 | 21 | 41 | 41 |
最优解是
- 获取尚未绑定共享带宽的所有EIP
- 选取带宽为带宽为21和20的EIP进入共享带宽
流量高峰需要缩容
流量高峰需要缩容的时候，一维的带宽起点=最小带宽=45（Mbps）
| 0 | 45 | 46 | 47 |
|---|---|---|---|
| 21 | 21 | 21 | 21 |
| 20 | 41 | 41 | 41 |
| 31 | 41 | 41 | 41 |
最优解是
- 共享带宽下其他EIP全部解绑
- 选取带宽为21和20的EIP进入共享带宽
有人问，为什么扩容和缩容一维起点要这么定义，直接定为最小带宽不好吗？
当然好，但是这样做的话，你得获取所有EIP的流量监控数据。而获取当前带宽只需要使用一个接口，之后绑定EIP到共享带宽即可，步骤少一点点。
最终成果发布在 GitHub
后记
在找局部最优解的时候我发现“背包剩余容量需要在其他元素里面排列组合，求和”感觉特别麻烦，就直接把第二维的EIP数据按照带宽升序处理再初始化二维数组。也就是说，这个二维的表格长这样：
1
2
3
4
5
6
7
00 40 41 42 43 44 45 46 47 48 49
02 02 02 02 02 02 02 02 02 02 02
05 07 07 07 07 07 07 07 07 07 07
10 17 17 17 17 17 17 17 17 17 17
15 32 32 32 32 32 32 32 32 32 32
20 35 35 35 35 35 35 35 35 35 35
21 35 41 41 41 41 41 41 41 41 41
虽然最后只是找到近似最优解，而不是最优解，但也算了。
结果并不重要，关键的是自己的思考。
