《算法导论》第三版 16.3-9怎么解啊？望高手指点！

《算法导论》第三版 16.3-9怎么解啊？望高手指点！

对于一个k字节的文件而言，合理的压缩应该得到一个不超过k字节的文件，也就是说我们假定对于任何一个文件压缩结果都不能变长
然后考虑所有长度不超过k字节的文件，这样的文件总共有T=256^k+256^{k-1}+...+256+1个，它们两两不同，总长度是L=k*256^k+(k-1)*256^{k-1}+...+1*256+0*1
把这些文件每个都压缩一下，得到T个新的文件总长度不超过L，且也必须两两不同（否则无法解压），真正的压缩结果应该得到总长度严格小于L的情况
但是由排序不等式知L是优化问题 min sum x_j*256^j 在约束条件0<=x_j<=256^j且 sum x_j=T 的最优解（这里0<=j<=k），取到这个最优解当且仅当 x_j=256^j，
（直观的讲法就是T个两两不同的文件总长度最短的情况只能是0字节的有1个，1字节的有256个，……，k字节的有256^k个）
所以压缩后总长度不变，也就是说没有真的压缩掉什么信息
追问：谢谢您等回答，但排序不等式那有点不太明白：
排序不等式是指
0 0 an×bn+a（n-1）×b（n-1）+......+a1×b1>=乱序和>=a1×bn+a2×b（n-1）+......+an×b1
这个不等式在这个问题中是怎么起作用的呢？
谢谢！
追答：排序不等式的作用是说明在约束条件允许的范围内，要使文件总长度最短，”小文件越多越好“
当然这一点比较显然，不用排序不等式也很容易说明
追问：明白了，我的想法在评论里，“追问”打不下。
再次谢谢您的回复。能加您qq吗？以后可能还有问题请教您。我的qq：407452979

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息！