实验五 背包有关问题和带时限的作业排序

实验五 背包问题和带时限的作业排序

一、实验名称：背包问题和带时限的作业排序

二、实验目的：掌握贪心算法解决问题的思想和一般过程，学会使用贪心算法解决实际问题。

三、实验内容

实验问题和程序运行结果：

第一部分 背包问题

1. 分析103页程序6-1，画出流程图。

2. 分析Knapsack类，私有变量，分别表示的含义为:

3. 分析greedyKnapsack程序，画出该算法的流程图。

4. 当背包为：

W	18	15	10
P	25	24	15

       M = 20 时：

       解数组的输出为：

5. 完善greedyKnapsack程序，使得输出解数组与原顺序相同。当背包的值为：

W	8	2	25	7	4	7	4
P	10	5	11	15	3	13	1

M = 45时，解数组的输出为：

 

第二部分 带时限的作业排序算法

1. 分析程序6-4，画出该算法的流程图。
2. 分析程序6-4，分别说明变量d、x、n、k、r的含义。
3. 当作业序列为：

时限	2	1	2	4	3
价值	100	10	15	27	9

       贪心算法的最终结果为：

1. 通过分析，或者在程序中增加适当的输入语句。以上题为例，给出在贪心算法的每一步解空间X的状态，以及j、r、k的值。

 

四、实验小结和心得：