Lesson11：近似算法
相对高效地得到近似解。
得到了一个近似比，是与规模相关的。
时间复杂度也是希望与近似比成多项式关系。
举例：装箱子问题。
- 在线算法：面对一个物品，立刻做决策。这是不能回溯的。
- 离线算法：全部看完了再做决策
在线算法难以利用算法来对抗数据分布模式。
对于所有的在线算法，装箱问题的近似比不可能小于\(\frac{5}{3}\)
离线算法处理箱子问题，我们可以注意到主要的trouble maker来自大物块。
因此我们不妨先把他们从高到低排个序。
又举例：背包问题
非常显而易见的算法就是计算出一个"性价比"，然后从高到低填入。
0-1背包：NPC问题
物品不能切割。
性价比排序还能得到最优解吗？
实际我们的算法是两个都试看看，也就是老师说的"混合贪心"。
重点在于理解整个算法，可分割意味着只有选择放入的物品中利润密度最低的(假设不小于2个)被分割。
那么我们讨论动态规划，状态转移方程可以这么写：
这理解应该简单，N就是考虑到的物品编号，M是剩余体积。
这里的\(O(N^2P_{max})\)并不代表该问题是成n多项式关系，由于\(p_{max}\)并不直接代表问题规模，我们把它换成"存储问题的比特/位数"才比较合理，因此\(p_{max}\)实际是一个2的幂次复杂度。
使得算法算的快一点，但是得到的已经是近似解了。
K中心点问题
给定n个点，然后要找出k个点，使得所有点与最近中心点的距离之和最小。
最大边际效应贪心
先放一个，求最小；
然后再放一个，使得减少尽可能多...
2r算法
从第一个算法发现，或者说本身这个问题，难点就在于点的"无限"位置。
我们假设圆心一定是在给定的点上面的，这样你的算法近似比不会大于2(因为对于我们所谓的圆内，点之间的距离不会大于2)可以证明就算是使用随机也不会大于2。
然而我们是不知道这个我们"给定"的r的，可以使用二分来解决。
"好的圆"算法
追求覆盖面积更小的圆，这是在2r算法的基础上的。
可以证明不大能获得2往下的近似比。
作业
FPTAS算法是那些时间复杂度符合\(O(n^{O(1)}(\frac{1}{\epsilon})^{O(1)})\)的算法。
虽然\(3^{\epsilon}\)看起来很恐怖，但是实际是个定值(笑)，看到\(n^2\)是个多项式时间复杂度就对了。