您好,欢迎来到华佗健康网。
搜索
您的当前位置:首页实验2 贪心法的应用

实验2 贪心法的应用

来源:华佗健康网
实验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) 请完成实验报告的编写,实验报告中要有详细的测试记录,包括各种可能的测试数

据。

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- huatuo0.com 版权所有 湘ICP备2023021991号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务