http://www.cnblogs.com/wuyuegb2312/p/3182896.html
要定义磁带上第n个文件，须要依次经过前面n-1个文件。假设磁带上有n个文件，长度分别为L[0],L[1], ..., L[n-1]且被访问的概率分别为P[0],P[1],...,P[n-1]，请问怎样安排它们在磁带上的存储顺序最好？
要定义磁带上第n个文件，须要依次经过前面n-1个文件。假设磁带上有n个文件，长度分别为L[0],L[1], ..., L[n-1]且被访问的概率分别为P[0],P[1],...,P[n-1]，请问怎样安排它们在磁带上的存储顺序最好？
分析：
最好的安排方式应该对应期望最小的方式。思考一下，不难写出期望的表达式：
（注意，访问第i个文件，因为要完整地读入这个文件，经过的长度是L[0]+L[1]+...+L[i]。
《编程之美》先探讨了两种简单情况：
P[0]=P[1]=...=P[n-1]，即概率相等时，把最长的文件放前面、最短的文件放后面L[0]>=L[1]>=...>=L[n-1]时，期望最小；
L[0]=L[1]=...=L[n-1]，即长度相等时，按概率大小从大到小排列，期望最小。
概率和长度都不同时怎么办呢？《编程之美》提出了一个折中方案，并举了L[0]=10,L[1]=6,P[0]=0.4,P[1]=0.6的例子来验证：
按照P/L由大到小排列构造序列。
P/L？嗯，确实综合考虑P和L两个因素了。其实有很多数学模型不都是这样嘛，将正相关的做分子，负相关的做分母。但这里是求解，而不是建模啊
在我们上文提到的贪心解也即按照P/L由大到小排列的序列中，我们考察其中i到j这一段，并采取把最末的j插入到i前面，i到j-1整体后移，即下图所示：
可以写出后者减去前者的期望变化量为：ΔE=L[j](P[i]+...+P[j-1]) - (L[i]+...+L[j-1])P[j]。由于P[j]/L[j]<=P[j-1]/L[j-1]<=...<=P[i]/L[i]，每个对应项相减都非负，其和ΔE也非负。我总结了一个规律：
更一般地，对于任意序列，如果其中存在一个子序列i...j且P[j]/L[j]最小，经过这样的调整，新序列对应的期望E总是不减的，而且当P/L不全相等时，新期望值总会增加。反之，如果做相反的操作，把P/L大的调整到前面，那么在没有相等的情况下，新序列的的期望总会减少，直到最后不能再调整，也即P/L从大到小排列时，期望E最大。
根据这个规律，就说明了为什么“按照P/L由大到小排列构造序列”获得的是最优解了。
太抽象、不好理解？No problem，拿一个例子来说明。
假定有一个P/L值为5、4、3、2、1构成的序列，那么在所有可能的排序中，5 4 3 2 1应该是最优解。而对于其他排列，比如2 3 5 4 1，用上面的方法调整为最优解的过程，就是其期望E不断变小的过程。这个调整过程是：
2 3 5 4 1 （1）原始序列，5调到2前面
5 2 3 4 1 （2）4调到2前面
5 4 2 3 1 （3）3调到2前面
5 4 3 2 1 （4）已经找不出序列i...j使得Pj/Lj大于序列中其他值，调整结束
这个调整过程看上去是不是很熟悉？没错，它和选择排序很像，殊途同归。我一开始没有想到这个期望最小化问题居然能和选择排序扯上了关系，直到挖掘到这一步。同时，用选择排序说明了，所有的序列最终都能转化成一个从大到小的排列，也即，所有序列转化成最优解时，对应期望E都在不断地减少（如果所有P/L都不等），“最优解”确实是最优解
类似题：
“将一个给定的自然数数组，连接起来得到一个数，求这个数的最大值或最小值”。
