背包问题贪心法.docx

该【背包问题贪心法 】是由【jiyudian11】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【背包问题贪心法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。背包问题贪心法
实验报告
学院:计算机科学与技术学院
班级:****
学号:
****
姓名:
****
一、实验目的
1)以背包问题为例,掌握贪心法的基本设计策略。
2)熟练掌握各种贪心策略情况下的背包问题的算法并实现;其中:量度标准分别取:效益增量P、物品重量w、P/W比值;
3) 分析实验结果来验证理解贪心法中目标函数设计的重要性。
二、问题基本思想描述
(1)贪心法的基本思路
从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。
该算法存在问题:
不能保证求得的最后解是最佳的;
不能用来求最大或最小解问题;
只能求满足某些约束条件的可行解的范围。
(2)背包问题的描述
已知有n种物品和一个可容纳M重量的背包,每种物品i的重量为叫。假定将物品i的一部分二放入背包就会得到P-X-的效益,这里,°-X--1,匕>0。显然,由于背包容量是M,因此,要求所有选中要装入背包的物品总重量不得超过M.。如果这n件物品的总重量不超过M,则把所有物品装入背包自然获得最大效益。现需解决的问题是,在这些物品重量的和大于M的情况下,该如何装包,使得得到更大的效益值。由以上叙述,可将这个问题形式表述如下:
工px
极大化目标函数
1<i<n
工wx<M
约束条件1<-<n
0<x<1,p>0,w>0,1<-<n
---
(3)用贪心策略求解背包问题
首先需确定最优的量度标准。这里考虑三种策略:
策略1:按物品价值p降序装包,
策略2:按物品重w升序装包
策略3:按物品价值与重量比值p/w的降序装包
算法描述
以策略3为例:
procedureGREEDY-KNAPSACK(P,W,M,X,n)
〃P(1:n)和W(1:n)分别含有按P(i)/W(i)>P(i+1)/W(i+1)排序的n件物品的效益值和重量。M是背包的容量,而X(1:n)是解向量。//realP(1:n),W(1:n),X(1:n),M,cu;
integeri,n;
X~0 〃将解向量初始化为零
cuJM//cu是背包剩余容量
foriJ1tondo
ifW(i)>cuthenexitendif
X(i)J1
cuJcu-W(i)
repeat
讦i<nthenX(i)Jcu/W(i)
endif
endGREEDY-KNAPSACK
三、程序流程图
以策略三为例:(此时物品已经按物品价值与重量比值p/w降序排列)
W(i)>cu
J
i<n
J
X(i)J1cuJcu-W(i)
X(i)Jcu/W(i)
i++
退出循环
物品i
程序结束
四、以策略三为例程序清单
#include<>
#include<>
structgood
{
doublev,w;//权值及重量
doublex;//解向量
};
voidcpygood(gooda,goodb){
=;
=;
=;
}
voidinsertionsort(good*goods,intn){
inti,j;
gooditem;
for(j=1;j<n;j++){
//cpygood(item,goods[j]);
=goods[j].v;
=goods[j].w;
=goods[j].x;
i=j-1;
while(>goods[i].v/goods[i].w&&i>=0){
//cpygood(goods[i+1],goods[i]);
goods[i+1].v=goods[i].v;goods[i+1].w=goods[i].w;
goods[i+1].x=goods[i].x;
i--;
}
//cpygood(goods[i+1],item);
goods[i+1].v=;
goods[i+1].w=;
goods[i+1].x=;
}
voidgreedy(intn,doublec,good*goods)
{ //n为物品数量,c为背包能承受的重量
doublem=c;
inti;
insertionsort(goods,n);
for(i=0;i<n;i++)
goods[i].x=0;
for(i=0;i<n;i++){
if(goods[i].w>m)
break;
goods[i].x=1;
m-=goods[i].w;
}
if(i<n)
goods[i].x=m/goods[i].w;
}
voidmain(){
good*goods;
intn,i;
doublec;
freopen("","r",stdin);freopen("","w",stdout);
scanf("%lf",&c);
scanf("%d",&n);
goods=(good*)malloc(n);
for(i=0;i<n;i++)
scanf("%lf%lf%lf",&goods[i].v,&goods[i].w,&goods[i].x);
greedy(n,c,goods);
printf("最终结果如下:\n");
printf("权重 重量 结果\n");
for(i=0;i<n;i++)
printf("%f%f%f\n",goods[i].v,goods[i].w,goods[i].x);
}
五、实验分析
(1)实例解答
设物品数量为n,背包承重量为m。n=7,M=15,(p「…'p7)=(10,5,
15,7,6,18,3),(wi'…'W7)=(2,3,5,7,1,4,1)。
各策略得到结果如下:
物品编号
策略一
策略二
策略三
1
1
1
1
2
0
1
2\3
3
1

1
4

0
0
5
0
1
1
6
1
1
1
7
0
1
1
背包最终权重
47
54

2)各策略所得结果分析
由上表可得,策略一以物品效益值的非增次序装包不能得到最优解,经过分析主要原因在于背包可用容量消耗过快;策略二按物品重量的非降次序将物品装包不能得到最优解,原因在于容量慢慢消耗的同时效益值未能迅速增大;策略三以单位效益为量度,是物品装入次序按比值的非增次序排列得到了最优解。
六、心得体会
通过本次实验我们了解了背包问题贪心法的基本思想和策略,我们发现用该方法解决此问题的核心在于对量度标准的选择,通过具体数据的解答,我们最终确定了以单位效益,即物品的权值和重量的比值为量度最终能得到背包问题贪心法的最优解,同时也使我们对贪心法这一策略有了更为直观的认识。