算法课程笔记
大二下的算法笔记
有关快排的讨论
不用交换的做法
利用一个和数组等长的空间。
把数组扫一遍，若a[i]
随便选个pivot，要不就选中间的数。
1 | int p=l,q=r-1,pivot=a[(l+r)/2]; |
大概这样。
设长为n的数组的时间复杂度是T(n)；开始推导：
$T(n)=\sum_{i=1}^{n-1}P_i(T(i)+T(n-1-i))+O(n) \\ O(n)是~partition算法的耗时，设~pivotpos落在0到~n-1的概率均等。 \\ T(n)=\frac{2}{n}\sum_{i=1}^{n-1}T(i)+O(n)=\frac{2}{n}S(n-1)+O(n) \\ S(n)=\frac{n+1}{2}(T(n+1)-O(n+1)) \\ S(n)-S(n-1)=T(n) \\ 2T(n)=2S(n)-2S(n-1)=n(T(n+1)-T(n))+T(n+1)+2n+1 \\ (n+1)T(n+1)=(n+2)T(n)-2n-1 \\ T(n+1)-(n+1)(2n-1)=\frac{n+2}{n+1}(T(n)-(n+1)(2n-1))$
我推不出来了，反正是o(nlogn)。
找第k大的数
跑partition，得到pivotpos。
若pivotpos==k，则返回pivot；
若pivotpos<k，则递归搜右半边；
若pivotpos>k，则递归搜左半边；
找中间数
对一个数：若前面的数都比它小，后面的数都比他大，则它是中间数。
找出一个数组所有的中间数。
对每一个数a[i]维护一个max[i]一个min[i]；
max[i]是从0到i（取到i）最大的数；min[i]是从n-1到i（取到i）最小的数；
从前向后扫一遍确定max，从后向前扫一遍确定min；
最后扫一遍，若max[i]==min[i]，则a[i]是中间数。
注意：对数组进行排序，中间数排序前后位置不变，但排序前后位置不变的数不一定是中间数。12345，54321，3不是中间数。
找最大最小的数
递归终止条件：若区间里只有2个数，则比较出结果。
先partition得到pivot；
对左半边跑【找最大最小的数】，对右半边跑【找最大最小的数】，得到lmin,lmax,rmin,rmax；
比较得到整个数组的最大最小。
赛马问题
有n匹马，比赛方法是每5个赛一次。想找出最快的3匹马，怎么办？
递归终止条件：若n<=5，则赛一次就找出123。
首先赛n/5向上取整（将其设为k）次，找出每一次的123。
然后对这k场的第一，再跑一遍【3匹马解法】，找到它们中间的123。
1那一场的2和3是23候选，2那一场的第二是3候选。也就是：
1 2 3
2 3
3
1已经确定了。第二第三的候选正好5个，再赛一场就行了。
复杂度
一开始赛k场是o(n)。然后是T(n/5)。最后一场是o(1)。
T(n)=o(n)+T(n/5)+o(1)。累加，o(1)累加是logn。
o(n)累加，n+n/5+n/5/5+…=n/(1-1/5)，还是o(n)？
那就o(n)了。
递归终止条件：若n<=5，则赛一次。
前面跟【3匹马解法】是一样的。只不过，是对这k场的第一跑一遍【5匹马解法】。
现在，我们对这k场的第一得到了12345。形势是：
1 2 3 4 5
2 3 4 5
3 4 5
4 5
5
1已经确定了。23赛一场也可以确定，和【3匹马解法】的赛法一样。
接下来，对各种23的情况一通讨论。就暴力讨论。最多再赛两次。
最近点对问题
k维空间内有n个点，找到距离最近的点对。
先nlogn排序，按x坐标排序。
递归终止条件：若区间里只有两个点，那就返回这两个点的距离。
mid=(xmax+xmin)/2，按照mid划分成左右两半。
对左右两半执行【最近点对解法】，得到左右两半的距离最小值。
令d为左右距离最小值的最小值。
考虑跨区间最近点对的可能性。若最近点对跨区间，则一个点在左边，一个点在右边。
无论如何，这两个点的横坐标离mid不应该超过d。
因此，对[mid-d,mid+d]里的点两两枚举，像二分图一样。比较这样得到的最小距离和d。
复杂度是nlogn。首先排序是nlogn。
然后递归深度是logn。去证每次合并的复杂度是o(n)。
感觉上最糟的情况是可以达到o(n^2)的，但事实上因为抽屉原理，有下面的结论：
考虑[mid-d,d]的点p，它的对应点q只可能在[mid,mid+d]*[yp-d,yp+d]上，这个区域里面最多有6个点，所以o(n)。
反证法，划成6个小长方形，如图所示： 若存在超过6个点，则必然有一个小长方形里面有2个（及以上）点，小长方形的对角线长度就是小于d的。 那么，左边的最近点对距离就是小于d的，推出矛盾。 https://blog.csdn.net/sinat_35678407/article/details/82874216
分形地对二叉树布线
对于一个高为h的满二叉树，将所有的节点布在一个网格纸的格点上，每个格点只能放一个节点。问怎样布线得到的图形所占的矩形面积（长*宽）最小？
分型。用四分来做。如图所示：
分形扩张的次数是h/2。长和宽都是o(2(h/2))的。因此面积是o(2h)的，大概。
我一开始的一点想法
一开始我觉得不能用分治做。考虑构造左子树和右子树的最优解，如果左子树占了某个格点，右子树就不能占这个格点了，即子问题之间是相互影响的。
换一个角度考虑：要想让左右子树不相互影响，应该怎么布线呢？可能会有帮助。
求凸包
给定平面上n个点，求一个最小的凸包，即一个顶点为给定点的凸图形，所有点要不在边上，要不在里面。
还是分治的思想，有点像最近点对。先把平面划分为左右两个半平面，对左右求凸包。
终止条件：若2个点或3个点。3个点显然三角形，或者正好共线就和两个点一样处理，总之把它们连起来。
现在合并左右的凸包。假设对于左右的凸包，我们已经维护了它们的一个逆时针方向的顺序的记录。
最后的大凸包由3部分组成：左凸包的左轮廓，右凸包的右轮廓，还有连接两个凸包的两条边。现在我们去找连接它们的边。
一个点在左边，一个点在右边。如果左边的凸包和右边的凸包都全部在这两个点连成的线的同一边，则这就是我们要找的线。能找到两条。
有这样一个结论：设右边的点为i。若i+1和i-1在连线同一侧，则右边的凸包就在连线同一侧了。
- 若它们在同一侧。画出i到i+1和i到i-1的射线，它们围出一个区域。因为是凸包，所以右边所有的点都在这个区域里。这个区域在线的一侧，ok。
- 若它们不在同一侧。即使某一侧只有i+1这一个点。如果将这条线作为轮廓，它就不是凸包了，会凹下去。如图。
因此【在同一侧】和【选这条线】是充要的关系。
依靠已经维护好的顺序记录，对于每一个边都可以用o(1)的时间判断是否可以。这有点像最近点对，合并时并不是每一个点都要两两算距离，并不是每一个点都要判断是否在直线同一侧。
如果找到了这个边，就顺势修改顺序记录，然后再绕着右边的凸包继续找第二条边。其实感觉上用链表记录可能会更好一点。
但是我不知道怎么找边。o(n^2)枚举吗？
对于合并：首先在左凸包上找到那个x坐标最小的点，将其作为原点。站在这个点往右看，找到张角最大和最小的两个右凸包上的点。这一步o(n)。
张角以逆时针方向为正，可以用正切代替。
从原点开始迭代，顺时针迭代。站在原点看，若【左凸包顺时针相邻的那个点】的张角不如【右凸包张角最大点】的张角大，则原点与【右凸包张角最大点】连线。去连下面的线。
若【左凸包顺时针相邻的那个点】的张角比【右凸包张角最大点】的张角大，迭代原点，原点变到【左凸包顺时针相邻的那个点】，我们接下来站在这个点看。重复上一步，直到可以连线。
下面的线同理，把角的比较条件从大换成小。
不用分治。首先在所有点中找到那个x坐标最小的点，将其作为原点。这一步o(n)。
站在这个点往右看，找到张角最大和最小的两个点，连起来。这一步o(n)。
站在【刚刚找的张角最大点】上，继续找张角最大点。直到到达【所有点中x坐标最大的点】。
站在【刚刚找的张角最小点】上，继续找张角最小点。直到到达【所有点中x坐标最大的点】。
此时已经构造好凸包啦。每次迭代o(n)，要迭代o(n)次，是o(n^2)。
棋盘覆盖
在一个2n*2n的棋盘上，有一个方格是奇异点。用L形的地砖来覆盖方格。
如果方格是2*2的，并且有一个奇异点，那么正好是L形，很好办。
如果是2n2n的，将其分为4块(2(n-1)2(n-1))的棋盘。在最中间填一个L形，保证每一个子棋盘都有一个奇异点，问题划分为4个小问题。
1 | int count=1; |
循环赛日程表
有N=2^n个运动员，要求每个人都与别的N-1个人赛一次，只能赛N-1天，排一个日程表。
为使问题更对称，假设第0天每个人要与自己赛一场。现在是赛N天了。
我们搞一个N*N的数组，表示第j天第i个人的对手。
1-N/2的人和N/2+1-N的人在前N/2天和自己这一组赛，在后N/2天和另一组赛。
和另一组赛的日程，就是和自己赛的日程，对手编号平移N/2。
1 | int ans[N][N];for(int i=0;i<N;++i)ans[0][i]=i; |
线性时间选择
给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。
其实前面好像写到排序里了，用partition方法。
1 | int partition(int l,int r){ |
所以pivot就是第pivotpos大的元素，如果pos>k，那么对(l,pivotpos-1)作partition；如果pos<k，(pivotpos+1,r)；如果pos==k，直接返回pivot。
时间复杂度真的是线性的吗？如果每次都选到中位数，那么只会找logn次…等比数列求和，总的来说会扫n个元素，因此是线性的。
如果选不到中位数？就强行使pivot=中位数。
贪心法
寻找区间最大子集
给出n个区间[l_i,r_i]，找出这些区间的一个子集，使得子集内的区间没有重合部分，并且数目最大。
按照r_i的大小（结束时间）排序，然后依次选择。如果下一个区间不与被选择的上一个区间重合，则选择它。
正确性证明
首先，一定要选排序后的第一个区间。如果选第一个还能选第二个，当然要选第一个了。
如果选了第一个就不能选第二个，那么在二选一里面还是要选第一个，结束的早后面就不那么被动了。
现在已经选了第一个。然后把和第一个冲突的区间去掉，得到新的序列，继续选第一个……
更严谨的一版：
某一个最优解里面一定包含第一个区间。反证法，假设最优解的第一个区间是第i个而非第一个。
如果选第i个之后还能选第1个，当然要选第一个了，这个最优解不是最优解，矛盾。
如果选第i个之后不能选第1个，为什么不选第一个呢，即使2-i的区间还是都不能选，至少i+1后的区间选择情况不会比最优解更差，毕竟1比i结束早。
然后把和第一个冲突的区间去掉，得到新的区间序列，继续选第一个……
最小生成树MST
prim和kruskal。
kruskal：不断地选择边权最小且不会与【已选择的边】成环的边。
prim：不断地选择边，选择从【已加入点的集合】连接到【未加入点的集合】的权值最小的边。
prim是直接反证就行了。设e是prim得到的 第一条 不在最优解中的边，最优解中连接prim的【已加入点集合S1】【未加入点集合S2】的边是w。把e加入最优解会得到一个环。
证明e比w好。S1连通，S2连通，直接把e换成w就会得到更好的MST。矛盾，得证。
要求无负权值边。
类似prim：不断地选择边，选择【未加入点的集合】中路径长度最小的边。贪心的规则变了。
路径长度：要求经过的点只能在【已加入点的集合】里。
基于这样的观察：全局最优由局部最优构成，若u到v的最优路径是u->…->a->…->v，则u到a的最优路径也是u->…->a。
因此，v的最优路径是【所有与v邻接的点的最优路径+它到v的边】中最优的。
然后我们反过来看：如何利用这个性质从原点开始迭代找最优路径？？
所有与原点邻接的点的最优路径要不就是别的什么，要不就是它与原点的连边。
如果是别的什么，那这个路径的第一步肯定也是和原点的连边啊。
所以与原点邻接的点中【与原点连边】权值最小的点，它的最短路径就是它与原点的连边。把它加入集合S。
再往下看：所有与集合S邻接的点的最优路径要不就是别的什么，要不就是【它与某已经确定最短路径的点的连边+那个最短路径（S中）】。
对【与集合S邻接的点】中，【它与某已经确定最短路径的点的连边+那个最短路径】最小的点，设为v。
设这个路径是u->…->w->v。
这个就是它的最短路径了！为什么呢？如果它是别的什么u->…->a->…->v，那么从u到a里面一定有一段是在S中的。再不济也要从原点出发吧！
设这一段为u->…->b->c->…->a。可以知道u->…->b->c不如u->…->w->v短。任何别的路径都不如现在这条短。
给定一些字符和频率，用01对这些字符进行编码，希望使平均码长最小。
正确性证明
叶节点都是字符。内节点的值为两个子节点值的和。
我们要构造一个二叉树，使得所有内节点的值的和最小。
首先，构造的二叉树中，不会有度为1的节点。不然把它的子节点提上来，立刻得到更优的解。
然后，频率越低的点越深，不然可以把它与更深且频率更高的点互换，立刻得到更优的解。
这样，频率最低和第二低的字符在二叉树里是兄弟。它们俩的父节点值为它们俩的频率之和。
我们拿掉这两个节点，改放上他们的父节点。然后以此类推，就构造了huffman树。
大概这样吧……
分礼物问题（不是正确解法）
有n个礼物，每个价值是vi，分给两个人，问怎么分才能使两人得到的价值差距尽量小？
错误解法
- 按价值从大到小排序；把第一个给A。
- 如果A比B少，下一个给A；否则给B。
19，16，9，8，8，8，8；
A：19，8，8=35；
B：16，9，8，8=41；
其实可以：
A：19，9，8=36；
B：16，8，8，8=40；
19，8，8=35
16，11，8，8=43
19，11，8=38
16，8，8，8=40
现在贪心解法和的比是4了。我不太清楚是不是approximation。
多机调度（不是正确解法）
N个机器，M个任务，每个任务耗时ti，希望完成所有任务总时间最短。
- 把任务按耗时从大到小排序；
- 把下一个任务分给当前总完成时间最小的机器。
这不就是后面那个makespan吗……
背包问题
给出n个物品，每一个有体积ci和价值wi，背包容量为C。要求 Σc <= C。希望Σw最大。
www三步走方法：
第一步：以什么为输入比较合适？就是dp数组的维度。
第二步：有什么可能的子问题？
第三步：总问题和子问题有什么关系？
建dp数组dp[i][s]，表示只从前i个物品中取，且取到的体积和为s时，最大的价值和。
这是神奇的思路啊，发现去决定第i个物品放不放，就要去观察前i-1个物品并且背包空间更小的情况。反正神奇。
初始化物品情况时，一定要从1而非0开始计数！！！
1 | memset(dp,0,sizeof(dp)); |
完全背包
每一种物品有无数个。
这是我的想法：
还是for i从1到n，考虑前i个物品。
然后对于s从C到0。我们现在看第i个物品。
如果放不下，那么就i-1，这个没有问题。
如果放得下？放一个，效果更好了。能不能再放一个？
为什么放一个会效果更好？感觉推不出感性的结论，就是那种【放一个效果好，那么就应该使劲放直到放不下】。
那么我们就一个一个放，直到再放一个效果不如原来。
1 | memset(dp,0,sizeof(dp)); |
会不会有这样的情况。我们现在一个不放。放了一个，发现更好了。放了2个，发现不如1个好。放了3个，发现比1个好？？
不会。把放3个的【放2个】换成【放1个的方法】，应该能立刻得到更优解，并且有趣的是这个最优解就是【放2个的方法】，还不如【放1个】好。
更高更妙的代码：从前向后遍历背包容量。
1 | memset(dp,0,sizeof(dp)); |
多重背包
bounded knapsack problem。
听说要对【每一个约束维度】+【限制取前i个】进行dp。
比如说最多选M个物品：
1 | memset(dp,0,sizeof(dp)); |
1 | memset(dp,0,sizeof(dp)); |
求方案总数
1 | memset(dp,0,sizeof(dp)); |
二维背包
输出最优方案
1 | memset(dp,0,sizeof(dp)); |
给出n个数，选某些数使得加和正好为C，可以做到吗？如何选？（给出的数不能重复用）
若dp[i-1][s]可以，或c[i]+dp[i-1][s-c[i]]可以，则dp[i][s]可以。
最长相同子序列
longest common sequence.
给两个字符串，返回最长相同子序列。只要是子序列就行了，不用连续。
dp[i][j]：取串1前i个字符，取串2前j个字符，最长是多长。
1 | for(int i=1;i<=l1;++i) |
www观察最优解：我们看串1，若1的最后一个与2的最后一个匹配，那么dp[i-1][j-1]+1。
若1的最后一个与2的前面的元素（不是最后一个）匹配，那么dp[i][j-1]。把2最后一个删了也没关系的吧。
同理，也要考虑dp[i-1][j]；
当做到ij的时候，i-1已经做完了；i，j-1也刚刚做完。因此递推是可行的。
选最大价值不重区间集
题目和贪心的版本差不多。是有n个区间，每一个区间有一个价值wi，要求选价值最大的区间集，并且它们在时间轴上不冲突。
约定dp[s]是0到s时间段内可以选的最大价值和的区间。
考虑第i个区间。默认的情况是不选。
然后如果end[i]<=s&&dp[s]<dp[start[i]]+w[i]，就dp[s]=dp[start[i]]+w[i]。
1 | memset(dp,0,sizeof(dp)); |
为什么是按照结束时间从早到晚排序呢？如果不是这样，递推合法吗？
我感觉现在这样的递推是合法的。
内层循环是遍历截止时间。
选第i门课不会影响start[i]之前的选课。start[i]之前的选课要在前面就被确定。要求所有在start[i]之前结束的课都被考虑过了。
那，结束时间早的课就要排在前面，所以就要按结束时间排序了。
分礼物问题
有n个礼物，每个价值是vi，分给两个人，问怎么分才能使两人得到的价值差距尽量小？
o(n*m)，m是价值总和：也就是希望其中一人得到的价值与m/2尽量相近，维护dp[i]表示其中一人得到价值i的分法。然后考察每一个礼物，递推。是背包问题，价值即重量，背包容量为m/2。
o(n^3)：维护一个集合（链表或bool，或int按位记录分法）表示可以得到的价值，最后找与m/2最相近的方案。如果m非常大，可以用这个方法。找与m/2最相近的方案：维护一个小于等于m/2的价值，遇到更接近m/2的方案就更新它。
感觉上，就是【找到价值与m/2尽可能相近的方案】思路的延伸。
如果要求一人只能拿n/2个礼物：
dp：维护dp[i][k]表示其中一人拿k个礼物得到价值i的分法，相当于限制背包物品个数。最后看dp[尽量靠近m/2][n/2]。o(n(n/2)m)。
o(n^3)：链表或结构体数组（下标为价值），记录礼物个数信息。每次礼物个数=n/2时，才比较价值是否更接近m/2，更新那个最优方案。
上台阶问题
这是个大水题了。有n个台阶，我们一串可以走1或2阶，有多少种上台阶的方法？
dp[i]是前i个台阶的走法。dp[0]=0, dp[1]=1; dp[i]=dp[i-1]+dp[i-2]。嗯。
最长上升子序列
有名的LIS问题：一个序列的子序列是可以不连续的，上升要求严格单调上升（不能等于）。
普通解法：设dp[i]是以i结尾的LIS的长度。对dp[i]，初始化为1，遍历前面所有元素，若有比它小的j就更新成dp[j]+1。o(n^2)。
更高更妙的解法：设dp[i]是长度为i的LIS的最后一个元素。对第k个元素，若大于等于dp[max_length]就dp[max_length+1]=k，若大于等于dp[j]且小于dp[j+1]就dp[j+1]=k，若比dp[1]小就dp[1]=k。
事实上啊，可以证明更高更妙的dp[i]是递增的数组。所以只会修改一个，修改一个就break出去。然后怎么修改这一个呢？二分查找！
此时复杂度已经是o(nlogn)！
最大子数组和
一个数列，求最大子数组和，这个【子数组】要求连续。
设dp[i]是以i结尾的最大连续子数组和。对第i个数来说，要不加入前面的子数组，要不自己作为开头起一个子数组。
dp[i]=max(dp[i-1]+a[i],a[i])。也就是若dp[i-1]<0，我就自己起头一个子数组。
回文最小划分次数
一个字符串s，切几刀才能让每个字串都是palindrome？如aab，切一刀，aa b。
居然是dp，可太神奇了。
记忆化搜索版本：
dp[i][j]=solve(i,j)是从i到j的字串的划分数。
dp[i][j]=min{solve(i,k)+1+solve(k+1,j)}。
如果ij是palindrome，solve=0，直接return；
自底而上递推版本：
dp[i][i+gap]，gap从1到n-1。
买卖股票
有一个代表股票价值的序列a，如果第i天买入第j天卖出的话，可以挣a[j]-a[i]。只有一笔钱，钱已经在股市中就不能买入了，卖出才能再买入。
一直找最长上升子序列？然后把各个子序列进行【选最大价值不重区间集】？
对！太有道理了！
最少编辑次数
编辑多少次才能使两个字符串相等，编辑包含增删改3种操作。
还是dp。dp[i][j]表示【串1前i个】【串2前j个】的编辑距离。
若a[i]==b[j]，dp[i][j]=dp[i-1][j-1]；
不等：
把a[i]删掉 或 给b[j]后面加一个a[i]：dp[i][j]=dp[i-1][j]+1；
把b[j]删掉 或 给a[i]后面加一个b[j]：dp[i][j]=dp[i][j-1]+1；
把a[i]改成b[j]：dp[i][j]=dp[i-1][j-1]+1；
就是最长相同子序列的递推公式。
博弈论
优化问题：系统的utility；博弈问题：个体的utility。
均衡：我不会再改变策略了，反正怎么改变也不会比现在更好。大家都不改变。
utility：(u_i(a_i,a_{-i}))；a_-i就是别人的策略。
voting game
假设第一排有10个座位，我们要选1个位置，对手要选1个位置。
对10个位置：离谁近就归谁。怎么选自己获得的位置最多？认为我们和对方同时选，选到同一个位置就平局。
在中间是最佳防守策略。貌似就是无论如何也不会比对方差的意思。
纳什均衡点。
所有玩家都不想改变自己当前的策略。
制胜策略
dominant strategy。
无论对方选择什么策略，我的这个策略总是最好的，相比于我的其他各种策略。相比均衡更强。
若 上：x，100；下：100，x；（两端路的通过代价，x是路上人数）总人数100。则上50人，下50人。
但是，若上下路的两段路之间有一个代价为0的高速公路，则x=100。
努力反而让局面变得更糟？
拍卖问题
有一个东西，拍卖方也不知道它的价格。希望设计一个策略，让理性人报出自己心目中的估价。
假设只有少数人知道它其实很值钱，少数人可以用相对低的价格赢得拍卖。现在看来好像就是要避免这种情况。
收益：若得到，ui=vi-c，估价-拍卖定价。若没得到，ui=0；
第一步，在纸上提交报价；
第二步，出价最高仍然赢；
第三步，付给我第二高的价格；
假设别人都定好将要出的价格了，我要定自己的价格。
若我的估价和别人的出价一起排序之后我的估价是第一，则直接出估价就能得到。没必要上调报价，因为反正付第二高的价格。不能下调，若下调就可能拿不到了，而拿到的收益肯定是正数。
若我的估价是第二，则上调之后要不拿不到，要不拿到了，但是这是要付原来那个第一的价格，那个价格比我估价高的……亏了。往下调无所谓，反正都是拿不到。
第三第四……的情况和第二一样。
只能得到第二高的价格+1（这时第二名如果继续加价就有可能亏）。拍卖方得到的收益差不多，但是不知道它的真实价格。
并且过程很慢。
P：多项式时间可解。
decision problem：比如说给出一些物品和背包大小，问装的价值能不能到达V，决策问题。
NP：在多项式时间内知道你给我的解是不是对/最优。
验证是否为因子和背包问题的decision problem（能不能达到V）都是NP问题。
归约reduction：A可以归约到B。B的一个特例是A。
approximation：对于没法在多项式时间内求出最优解的问题，NP难。
CIRCUIT-SAT（circuit satisfiability）是NP问题，所有NP问题都可以归约成它。
和它难度一样的问题还有无数个。NPC：circuit-sat属于它，所有属于它的问题都可以互相归约。
相关定义
感觉这个是可能考的。
- P：可以在多项式时间内找到解法的问题；
- NP：可以在多项式时间内确定一个答案是否正确的问题；
- NPC：NP完全问题，是一类NP问题，所有NP问题都可以归约到它们。
- NP hard：所有的NP问题都可以归约到它，但它不一定是一个NP问题。
- 归约：A归约到B，A是B的特殊情况，会解B一定会解A。
knapsack
在ci vi属于整数时，是可以在多项式时间解决的。
但是实数呢？NP难。NP-hard。
贪心：
按照性价比选？无穷坏
比如C=1；
10^-7 1
1 10^7-0.0000001
很坏。
按价值最大贪心？无穷坏
C=1;
1 100
10^-7 60
……
10^-7 60
max一下上面两个算法
是可行的。那么c是多少？然而我们不知道OPT。
我们尝试寻找OPT的上界。c<=OPT上界/ALG<=OPT上界/ALG下界。放缩。
OPT(sigma)<=ALG1+vmax
ALG3>=(ALG1+ALG2)/2>=(ALG1+vmax)/2，因为vmax一定会被ALG2选。
那么，c<=2了……
OPT(sigma)<=ALG1+vmax怎么来的？？
证明：设按照性价比贪心第一个装不下的物品的价值是vl，
则OPT<=ALG1+vl<=ALG1+vmax，就得到了。
设装入ALG1+vl所需的容量是Cl，那么这个方案就是OPT|容量=Cl。
OPT|容量=Cl > OPT|容量=C。
或者这样说，我们引入FOPT（fraction OPT，此时物品可以随便切割）。
OPT|容量=Cl > FOPT|容量=C > OPT|容量=C。
另一个神奇的做法
来源：https://www.cnblogs.com/cy0628/p/14023341.html；
输入ε>0, 令m=向上取整[1/ε]. 首先我们取 t=1:m 个物品(遍历Cnt种取法), 然后对剩下物品应用ALG1(性价比贪心).
它的近似比为1+ε。
均衡问题
makespan最大完工时间。
n个任务，每个任务有一个长度li，可以分到m台机器上，每台机器任务总长度是Li。
要min{max Li}。
贪心，动态调度思想，每次放到目前完工时间最小的那个机器上。
这个不是最优解，如按照1 10 100的顺序放：
100
1 10，现在是101。
其实是：
10
1 100，makespan是100。
现在开始放缩：
OPT >= max{(Σli)/m,lmax} >= ((Σli)/m+lmax)/2; 可以理解。
ALG <= (Σli)/m+lmax;
考虑最后一个，它肯定被放在目前最矮的机器上，这台机器是<= (Σli)/m的。
然后放上最后一个，最后一个比lmax要矮。就得到了。
万一最后一个放完了之后这个机器并不是最大makespan呢？
一些顾虑和我们的想法
应该是先按照从短到长排序然后再动态调度吧。
数归：假设m个机器时，对于k=1到n-1的情况，都有最后放任务的那个机器最长，证k=n。
我们已经按照任务长度对任务升序排序并重新标号，最长的任务是n。设放最长的任务的机器是m1。
反证法：设放完最长的任务n后，还有一个机器m2比m1更长。去推矛盾。
设m2顶端是任务j，m1放n前顶端是任务i。（若m2顶端无任务，则不可能比m1长。若m1的n下无任务，可以认为是长度为0的任务。）
若i比j先放，即i比j短。那么根据规则，m2放j之前比m1短（每次挑最短的放）。m2原来比m1短，m2再放一个j，m1再放一个n。显然m1长于m2，矛盾。
若j比i先放，即j比i短。那么根据数归，放i之后m1已经比m2长了，但是m2顶端就是以前放的j，再往m1上放n不符合规则，矛盾。
进而可推出结论，某机器顶端任务一定比另一个机器非顶端任务后放。即，往某一机器放两个任务的间隔中，其他机器一定都放过任务了。
数归：一定是一轮一轮放任务
假设前m个任务按照1到m的顺序放，这个没问题。
设现在放km+x个任务，那么应该放在第x个机器。
如果放在第y个机器，y<x。y上已有k+1个任务，x上有k个任务，y的顶端k个任务比x的顶端k个任务每个长度都大，y还多最底端那个任务。y的长度大于现在的x（未放km+x的x）。
如果放在第y个机器，y>x。y的k个任务比x的k个任务每个长度都大。y的长度大于现在的x（未放km+x的x）。
所以只能把km+x放在x上。
若x=m呢？同理只能放在第m个机器，只是不用考虑“y>x”了。
在线算法online
若信息是一点一点被告诉的。
假设有一堵很长的城墙，我站在原点，知道某一个地方有一个门，去找门。
先往右走1，然后回到原点，然后往左走2回到原点，然后往右走4回到原点，往左走8回到原点，…
c可以到12。
牌面值为1到13（可重复），陆续发牌给我看，我决定要不要这张牌。我只能要3张。目标是最大化a1+a2+a3；
对任意情况都有OPT/ALG<=c。要考虑比较极端的情况。
第一张不会是13或1。最后一张给1。
解法
min{13/ALG, ALG/1}，在一张牌的情况下。如果我要了这一张，接着出13。如果不要，最后出1。
sqrt(13)。若比sqrt13大，就拿。若不大于sqrt13，等。
所以3张牌怎么办？？每次发牌都是独立的吧，大概。
阿尔卑斯山滑雪
买或租滑雪装备。买15k，租1k/天。
解法
租到第15天，然后买设备。c=2。
天数小于15时，我们是OPT。天数大于15时，c=2。
关灯问题
随机叫同学进一个屋子，屋子里有k个灯。我们有n个同学。
灯在外面是看不见的。同学在屋外不能交流。
每个同学进屋之后可以操作灯，下一个同学会看到操作后的状态。
问：什么时候可以确定每个同学都进屋一次？
首先：若一个同学第二次进入屋子，不要改变灯的状态。
设log2(n)向上取整个灯，做二进制加法。
一个灯的情况：事先商量一个关灯的同学。
一个不关灯的同学进入屋子，若：1. 灯是关的；2. 自己原来没开过灯，则开灯；
若关灯同学进屋时发现灯是开的，则关灯，count++。count一开始是0。
若count==n-1，则每个同学都进屋一次。