第四章上机实践报告
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案， 使得能够在磁带上存储尽可能多的程序。 对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数。
n表示文件个数，L表示磁带的长度。后面有n个磁带每个磁带的长度，看下最多能存储多少个磁带。
满足题目要求，即磁带数要最大，且总磁带长度要小于L。利用贪心算法的思想，将所有的磁带进行排序，优先选择长度最小的磁带。这样即可装入更多的磁带。
利用反证法证明应该优先选择长度短的，假如有两个磁带a，b，La>Lb。选择磁带a，则最优解包含了磁带a，可是磁带b比a更短，装磁带b的话有可能可以放入更多的磁带。证明应该优先选择长度短的磁带。
时间复杂度为O（nlogn），使用了快速排序。
空间复杂度为O（n），使用了一维数组存放各磁带长度。
题目还是比较简单的，注意下边界条件，如全部磁带都可以放进去的情况。
原文：https://www.cnblogs.com/tinyea/p/11881382.html