1.实践题目：
程序存储问题
2.问题描述：
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案， 使得能够在磁带上存储尽可能多的程序。 对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数。
3.算法描述：
因为要尽可能装在更多的程序，所以贪心算法的选择基准为程序在磁带上的长度，优先选择长度短的程序。
①贪心选择性质：
设程序已经参照长度从小到大排序，（x1, x2, ..., xn）是程序储存问题的一个最优解，设k = min(1<=i<=n) {i | xi = 1}，如果给定的程序存储问题有解，则1<=k<=n。
当k = 1时，(x1, x2, ..., xn)是一个满足贪心选择性质的最优解。
当k > 1时，取y1 = 1，yk = 0，yi = xi，1<i<=n，i≠k，则（n∑i=1）liyi = l1 - lk + （n∑i=1）lixi <= （n∑i=1）lixi <= L
因此，(y1, y2, ..., yn)是所给程序存储问题的可行解。此外，由（n∑i=1）yi = （n∑i=1）xi知，(y1, y2, ..., yn)是满足贪心选择性质的最优解。所以，程序存储问题具有贪心选择性质。
②最优子结构性质：
设（x1,x2,x3,...,xn）是程序存储问题的满足贪心选择性质的最优解，则x1 = 1，(x2,x3...,xn)是磁带容量为c - w1，待装载程序为{2，3，4...,n}时相应最优程序存储问题的解。也就是说，最优程序存储问题具有最优子结构性质。
4.算法时间及空间复杂度分析（要有分析过程）
算法时间复杂度：O(nlogn) —— 快排的时间复杂度为：O(nlogn)，排序好后贪心选择过程时间复杂度为：O(n)，故综合来看算法时间复杂度为O(nlogn)
空间复杂度：O(n)——因为需要长度为n的数组来存储每段程序的长度。
5.心得体会（对本次实践收获及疑惑进行总结）
贪心算法比之前学的动态规划以及分治法要来的简洁，更为直接。但在利用贪心算法前，要理清好思路，确定好选择的标准，并且一以贯之。同时在利用贪心算法这一思想的时候，会感觉比动态规划实现起来要麻烦不少，经常要借助栈等数据结构。
原文：https://www.cnblogs.com/lh6666/p/11877259.html