贪心算法设计技术的应用

注意：闽工院计算机系07届请勿下载，以免被老师发现 1．利用贪心策略解决背包问题。现有载重为M公斤的背包和n种货物。第i种货物的重量为Wi，它的总价值为Pi，假定M、Wi、Pi均为整数。设计程序给出装货方法，使装入背包的货物总价值达到最大。 2．设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结账，收银员具有面值为100，20，10，5和1元的纸币和各种面值为5角、2角、1角的硬币。设计程序计算顾客各种所买商品的钱数，并根据顾客所付的钱数输出零钱的数目及要找的各种货币的数目。 3．利用贪心策略解决磁带存储问题。有n个程序需要存储在磁带上，它们的长度分别是L1,L2,…,Ln，它们使用的频率分别为F1,F2,…,Fn，求程序在磁带上最佳存储顺序，使平均检索时间最少。