非准程序员请绕道，这篇文章不是你想看的。（而且很长，虽然满满的干货）
写下这个字的时间点是23:53，是时候关掉电脑钻进被窝戴上耳机听会歌准备入睡了。或许是睡意还不太明显，毕竟放假整天吃吃喝喝睡睡嘛，脑洞就闪进了一个问题，你想听歌啊？听多久？歌单怎样选最好？
这样，问题就来了。。。
睡前歌单
我网易云歌单有539首歌，现在要从中选出一些今晚要听的歌来组成睡前歌单，如果我给每首歌标上喜欢程度（真希望网易云给加上这个功能），星级从一到五。而且听歌时间不能多于一个小时。那，怎样选才使自己最满意呢？
显然，衡量满意度的标准就是选上的歌的喜欢程度的星级总和。记为S。
这个问题并没有我文字描述的那样无聊和简单，暴力破解的方法当然可以把睡前歌单给弄出来，把所有歌都组合一遍，选出既满足总时间长度小于一个小时又星级总和最高的不就搞定了吗！？对啊，这样当然可以，然而，算算运算量是多大吧，n首歌就是O(2n)的运算量，我有539首歌就是2539量级的运算量啊，全世界的人帮我算我今晚甚至这辈子歌也是听不成了！
来来来，程序员入场，分析一下选歌过程吧。
总歌单是已经有的，记这个歌单为Like，歌单排列第i的歌表示为Like[ i ]，歌曲长度为Like[ i ].Length，星级为Like[ i ].Star，听歌时间记为T（为简化问题，假设时间的最少长度均为1s，即都是整数）。
现在，我们从歌单Like上的第一首歌来慢慢分析，第一首歌选不选呢？选的话，这首歌要占去Like[1].Length的时间，而S增加了Like[1].Star，然后我们再考虑T-Like[1].Length时间下选不选Like[2]。不选的话，那跳过它，我们继续考虑是否选Like[2]。咦，选或不选之后，我们好像又是要重复考虑选或不选哦，递归！最优子结构啊！动态规划可以来解决这个问题！
动态规划
动态规划（Dynamic Programming），一般称DP。
对于某一类问题，我们可以用DP方法来解决。《算法导论》中是这样说的
1.刻画一个最优解的结构特征
2.递归地定义最优解的值
3.计算最优解的值
4.利用计算出的信息构造一个最优解
算法导论上的表述很是通俗，其实对于DP，核心是两个东西，一个是状态的定义，一个是确定状态转移方程。
状态是什么？就是问题本身，我们怎样描述这个问题，就是在描述这个状态。
状态转移方程是什么？就是从问题到子问题的状态转移，对应于上面的第2点，一般形式就是递归方程。
一台计算机，归根到底就是一台状态机，我们把一个状态输入进去（比如2+2），状态机通过某种方法，将状态转化为一个更易解的状态（比如变成了1+1+1+1），依次下去，直到得出解。这个就不展开说了，可参见：有限状态机-维基百科
回到我们的问题。现在我们来定义状态，对于时间为T(单位秒)的听歌时间，有N首歌，定义MaxS[N][T]：在前N首歌中选择歌单，使其总长度不多于T，使S(星级总和)最大。最大值就记为MaxS[N][T]。对应我的歌单，最优解就可表示为MaxS[539][3600]，在前539歌中选择歌单，使其总长度不多于3600秒，并使S最大。这里我用了二维数组来表述，是为了说明在实际代码中我们可以用二维数组来直接表达这个状态。
接下来就是重中之重的状态转移方程，我先直接写出来：
MaxS[N][T]=max{ MaxS[N-1][T] , MaxS[N-1][T-Like[i].Length] + Like[i].Star }
上面这鬼式子什么意思呢？在N首歌中选择，那第N首选不选？不选的话，则状态变为MaxS[N-1][T]，因为现在我们要从前N-1首歌中选了，而可以听的时间依然不变，并没有减少。而选呢，那么状态变为MaxS[N-1][T-Like[i].Length]，因为依然要继续从剩下的N-1首歌中选，可以听的时间也减少了Like[i].Length，而S增加了Like[i].Star。选或不选哪个最大？最大的那个自然就等于MaxS[N][T]，状态转移方程就这样出来了。
借助状态转移方程，就可以动手码代码了。
其中核心伪代码如下，初始条件是当i等于0时，MaxS均等于0。
for i=0 to N
for j=0 to T
MaxS[i][j]=MaxS[i-1][j]
if j >= Like[i].Length and MaxS[i-1][j] < MaxS[i-1][T-Like[i].Length] + Like[i].Star
MaxS[i][j] = MaxS[i-1][T-Like[i].Length] + Like[i].Star
上面的伪代码表现的是自底向上的动态规划算法，时间复杂度显然是O(N*T)。好像比O(2^N)少了好多了诶。
在上面伪代码循环完成后，我们只要在后面加一个for循环，比较所有MaxS[i][j]和MaxS[i-1][j]，如果前者大于后者，则第i首歌是要选的，否则，第i首歌是不选的，这样最优解就构造出来了，这个过程复杂度是O(N)，所以整个过程时间复杂度还是O(N*T)。
动态规划一般之所以能大幅度减少运算时间，是因为其递归分解出来的子问题有很大一部分是重叠的，我们称之为重叠子问题。在朴素算法中，由于不对重叠子问题做处理，而是直接暴力运算，所以导致时间复杂度一般为指数型的，比如前面说到的组合来求解睡前歌单，复杂度为O(2*N)，而动态规划则利用空间换时间的思想，将所有遇到的子问题的运算结果都保存下来，这样，接下来的运算中，如果遇到了同样的问题，则直接得到结果而不用再算一遍，所以一般能将时间复杂度降到多项式时间。能运用动态规划来快速解决的问题一般具有两个要素：最优子结构，重叠子问题。最优子结构保证了能用动态规划算法，重叠子问题保证了动态规划算法具有很好的时间复杂度。在上面的伪代码中，我们自底向上，利用二维数组保存运算数据，类似的问题一般也是这样做的，当后面想要获取MaxS[i-1][j]的值的时候，我们已经计算好并只计算了一次这个值，直接给就行了，所以时间复杂度就大幅降低变成O(N*T)了，今晚就能算完开始听了哈哈哈哈。。。。。
冷静冷静
好像哪里不对，运用动态规划能降低时间复杂度是因为具有大量的重叠子问题，在上面的伪代码中，有哪些数组的值我们需要用到至少两次的？？？好像并没有啊！基本都只用到了一次啊！！！妈蛋问题又来了。
在上面的伪代码中，只有在很巧合的情况下，某些数组的值会被用到两次，比如某首歌的时间长度为0，或者其中一首歌的长度恰好为另外两首歌的长度之和。其实，在写状态转移方程的时候，我就觉得那式子的形式很眼熟了。现在细看，不就是背包问题的状态转移方程吗，两者是等价的好吗。。。而背包问题是著名的NP完全问题。
NP完全问题
P类问题是指能在多项式时间内解决的问题，即O(n^k)，比如排序，我们能在O(nlgn)时间内解决。
NP类问题是指能在多项式时间内被证明的问题。
P明显是NP的子集，进一步的，P是否是NP的真子集？即P是否等于NP？答案就不那么显而易见了，这个问题其实是当今最难的问题之一，你能给出答案，你就能走上人生癫疯~
对于很多问题，如果我给出一个解，一般你都能在多项式时间内证明这个解是不是最优解，即NP类问题，然而，要在多项式时间内直接给出这个问题的最优解，就不是一个简单的事情了，如果这个问题很难很难，目前并没有多项式时间的解决算法，我们称之为NP完全问题（NP-Complete,NPC），你能在多项式时间内解决一个NP完全问题，就能在多项式时间内解决所有的NP完全问题，然后你的奖金能在北上广深买很多很多好吃的，相信我:)。
我们的选歌单问题是NP完全问题吗？很不幸，是的。选歌单问题和0-1背包问题是等价的，两者的复杂度形式都是O(x*y)，看起来是多项式时间，其实并不是，通俗的理解，我们的歌曲数量是一首一首数的，那输入数据规模就是一首一首增加的，而T是什么鬼？是时间啊，谁说时间跟歌曲数量是多项式相关的？从而得出结论是多项式时间的？Naive!
造物主说，时间在计算机中是以二进制表示的，所以时间的输入数据长度其实是lgT=B，所以O(N*T)=O(N*2^B)，哭了，是指数增长的。对于这种看起来是多项式时间算法，实际并不是的，称之为伪多项式时间算法，同样是伪多项式时间算法的还有素数求解算法等。
所以，又回到最初了，不管是直接组合暴力求解，还是动态规划求解，时间复杂度均是非多项式的，所以能不能在睡前挑选完歌单，随着听歌时间长度和歌曲数目的增加，需要的挑选时间均是爆炸性增长的。然而，动态规划依然是这个问题的最优解法之一，虽然同是指数增长，但是动态规划的求解比组合暴力求解需要的时间还是大大减少的。两者至少不是同一个量级的。所以对于背包问题，我们一般也是用动态规划来求解的。这里可以看出，利用重叠子问题从而可以空间换时间的性质并不是动态规划的本质，仅仅是锦上添花而已，动态规划的本质是利用最优子结构递归求解，专业的讲是：对问题状态的定义和状态转移方程的定义。
那，怎样？有没折中的方法？保证在不管时间长度和歌曲数量多少的情况下，我都能今晚就挑选出歌单。。。。
贪心算法
可以用动态规划，当然就能用贪心算法了，算法导论中是这样表述的：
1.将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。
2.证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。
3.证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
又是啰里啰嗦的表述，简单明了可以这样说，对于一个问题，我们做出当下看起来最好的选择，然后继续求解剩下的唯一的子问题。
那选歌单的贪心算法是怎样的呢？
很容易想到，要想S值最大，则听歌过程每一秒获得的Star值应该尽可能的大。
对于歌曲Like[i]，听它的时候，每一秒获得的Star值是Like[i].Star / Like[i].Length。将这个值记为Like[i].StarPerSecond。
利用StarPerSecond进行从大到小排序，然后贪心算法就启动啦，排最前的肯定选啊，然后选第二的，然后选第三的，，，，直到听歌时间用完了，挑选也就完成了。时间复杂度是O(n)，靠，多项式时间就这样出来了。
那，这样选出来的歌单是最优的吗？
不是的，贪心算法只能保证取得次优解而不能保证最优解。只有在踩到狗屎运的情况下，才能取得最优解。
我们这样选出来的歌单，只能使最后取得的S'接近最大值S，而不能保证取得S'=S。
毕竟我的歌单Like有很多歌而且要听一个小时，我就选贪心算法吧，牺牲那么点满意度换取大量的时间值得了。
对于NP完全问题，我们一般也是采用近似算法来取得多项式时间，而不强求一定要取得最优解。
至于为什么不能保证S'=S
证明，略:)
原文转自谢培阳的博客
网友评论