实验2 贪心法的应用

1.实验目的

（1） 理解贪心法的思想。 （2） 掌握用贪心法解决问题

2.实验类型

设计型

3.预习要求

掌握教材上贪心法的思想，复习学过的相关用贪心法策略求解问题的算法

4.实验基本要求

（1） 仔细阅读实验的题目，设计的程序要满足正确性，代码中有关键的注释，书写格式

清晰，简洁易懂，效率较高，适合各种合理输入，并能对不合理输入做出正确的提示。 （2） 实验题目：

a) 背包问题

 问题描述

要求选择物品，尽可能让装入背包中的物品总价值最大，但不能超过总容量。  编程任务

利用贪心法策略设计一个算法对任意输入的n个物品的重量和价值以及背包重量m，编程输出使得选择物品总重量不超过m但总价值最大的物品选择方案  数据输入

第一行输入物品的个数n，第二行输入n个物品的名称，第三行输入n个数表示每个物品的重量，第四行输入n个数表示每个物品的价值，第五行输入背包的重量  结果输出

输出最大值和次大值。

输入示例 7

A B C D E F G

35 30 60 50 40 10 25 10 40 30 50 35 40 30 150

输出示例 A:0.00 B:30.00 C:0.00 D:50.00 E:35.00 F:10.00 G:25.00

b) 多机调度问题  问题描述

要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。  编程任务

利用贪心策略试设计一个算法得出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。  数据输入

第一行输入作业的个数n，第二行输入n个作业的序号，第三行输入n个作业的处理时间，第四行输入机器的数目m，第五行输入m台机器名称。  结果输出

程序运行结束时，输出第调度方案。

输入示例

7

输出示例 M1:4 M2:2 M3:5 M3:6 M3:3 M2:7 M3:1

1 2 3 4 5 6 7 2 14 4 16 6 5 3 3

M1 M2 M3

 实现提示

贪心选择策略：最长处理时间作业优先。

如果作业数目n比机器的数目m少或相等，则直接把作业分配下去。如果作业数目n比机器的数目m多，则依照处理时间由大到小给空闲机器。

按照指定的格式书写实验报告，实验报告清晰，但不赘述，字体最大为四号。在实验结束一周内上交实验报告。

5.实验基本步骤

（1） 仔细阅读实验要求，设计好输入输出，按照贪心法的思想构思算法，选取合适的存

储结构实现应用的操作。 （2） 设计的结果应在Visual C++ 实验环境下实现并进行调试。

（3） 请完成实验报告的编写，实验报告中要有详细的测试记录，包括各种可能的测试数

据。