贪心法计算背包问题.docx

该【贪心法计算背包问题 】是由【国霞穿越】上传分享，文档一共【4】页，该文档可以免费在线阅读，需要了解更多关于【贪心法计算背包问题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。计算机科学与工程学院学生实验报告
学号
专业
班级
姓名
课程名称
课程类型
实验
实验名称
贪心法设计实验
实验目的:
1、以背包问题为例,掌握贪心法的基本设计策略。
2、熟练掌握其中各种贪心策略情况下的背包问题的算法并实现。
3、分析实验结果来验证理解贪心法中目标函数设计的重要性。
实验内容:
贪心法把一个复杂问题分解为一系列较为简单的局部最优选择,每一步选择都是对当前解的一个扩展,直到问题的完整解。贪心法的典型应用是求最优解问题。
二、设计思想
贪心法在解决问题的策略上目光短浅,只根据当前已有的信息做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。
三、实现过程
1、【问题描述】
给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,但不可以重复装入。
2、【想法】
用贪心法求解背包问题的关键是如何选定贪心策略,使得按照一定的顺序选择每个物品,并尽可能的装入背包,直至背包装满。至少有三种看似合理的贪心策略:
1)按物品价值v降序装包,因为这可以尽可能快的增加背包的总价值。但是,虽然每一步选择获得了背包价值的极大增长,但背包容量却可能消耗太快,使得装入背包得物品个数减少,从而不能保证目标函数达到最大。
2)按物品重量w升序装包,因为这可以装入尽可能多的物品,从而增加背包总价值。但是,虽然每一步选择使背包得容量消耗得慢了,但背包价值却没能保证迅速增长,从而不能保证目标函数达到最大。
3)按物品价值与重量比值v/w的降序装包。
3、【图解过程】
x[i]=C/w[i]
物品i
x[i]=1
C=C-w[i]
i++
退出循环
程序结束
0
53Iks赏Ej纂的的口置物背AA
11lr・:
9S
M效的的品口HD卜TI卜Tfin
AA
務
-*%r~-
R522■■-・・
1的的22
1
入入
035
■■.
011---♦*♦#放放放毛3050??,:那育甘..于也・"N-h_MUtts
123
4、【代码分析】
intKnapSack(intn,intw[],intv[],intC)
{
doublex[10]={0};
intmaxValue=0;
for(inti=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];
returnmaxValue;
实验总结:
通过本次实验我们了解了背包问题贪心法的基本思想和策略,我们发现用该方法解决此问题的核心在于对量度标准的选择,通过具体数据的解答,我们最终确定了以单位效益,即物品的权值和重量的比值为量度最终能得到背包问题贪心法的最优解,同时也使我们对贪心法这策略有了更为直观的认识。
实验成绩
教师签名