实验总结：
通过本次实验我们了解了背包问题贪心法的基本思想和策略，我们 发现用该方法解决此问题的核心在于对量度标准的选择，通过具体数据 的解答，我们最终确定了以单位效益，即物品的权值和重量的比值为量 度最终能得到背包问题贪心法的最优解，同时也使我们对贪心法这一策 略有了更为直观的认识。
实验成绩 教师签名
计算机科学与工程学院学生实验报告
学号 课程名称 实验名称 实验目的： 贪心法设计实验 专业 班级 课程类型 实验 姓名
1、以背包问题为例，掌握贪心法的基本设计策略。 2、熟练掌握其中各种贪心策略情况下的背包问题的算法并实现。 3、分析实验结果来验证理解贪心法中目标函数设计的重要性。
实验内容：
一、实验概述
给定 n 种物品和一个背包。物品 i 的重量是 Wi，其价值为 Vi，背包 的容量为 C。应如何选择装入背包的物品，使得装入背包中物品的 总价值最大? 与 0-1 背包问题类似，所不同的是在选择物品 i 装入 背包时，可以选择物品 i 的一部分，而不一定要全部装入背包，但 不可以重复装入。 2、 【想法】
3、 【图解过程】
物品 i
w[i]>C
x[i]=1 C=C-w[i]
i++
i<n
退出循环
i≤n
x[i]=C/w[i]
程序结束ቤተ መጻሕፍቲ ባይዱ
4、 【代码分析】 int KnapSack(int n,int w[],int v[],int C) {
double x[10]={0}; int maxValue=0; for (int i = 0; w[i] < C; i++) { x[i]=1; maxValue+=v[i]; C=C-w[i]; } x[i]=(double)C/w[i]; maxValue+=x[i]*v[i]; return maxValue;
用贪心法求解背包问题的关键是如何选定贪心策略， 使得按照一
定的顺序选择每个物品，并尽可能的装入背包，直至背包装满。至少有 三种看似合理的贪心策略： 1）按物品价值 v 降序装包，因为这可以尽可能快的增加背包的总价 值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却 可能消耗太快，使得装入背包得物品个数减少，从而不能保证目标函数 达到最大。 2）按物品重量 w 升序装包，因为这可以装入尽可能多的物品，从而 增加背包总价值。但是，虽然每一步选择使背包得容量消耗得慢了，但 背包价值却没能保证迅速增长，从而不能保证目标函数达到最大。 3）按物品价值与重量比值 v/w 的降序装包。
贪心法把一个复杂问题分解为一系列较为简单的局部最优选择，每 一步选择都是对当前解的一个扩展，直到问题的完整解。贪心法的典型 应用是求最优解问题。
二、设计思想
贪心法在解决问题的策略上目光短浅，只根据当前已有的信息做 出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都 不会改变。
三、实现过程
1、 【问题描述】