贪婪算法装箱问题等练习

《贪婪算法装箱问题等练习》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、贪婪算法练习练习题1：考虑1、8、9、11这四种面值的硬币，要找出币值24的零钱，怎么找能使硬币数最少？利用matlab编程求解。解：设为二进制变量，如果硬币j被选中，则，=1，否则=0，则找硬币问题的数学模型如下：min；；用贪婪算法求解，其MATLAB程序如下：function[n,x]=payback(v,y,m)[m,n]=size(y);fori=1:nforj=1:n练习题2：利用matlab编程FFD算法完成下题：设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。funct

2、ion[nbox,p]=sjy(n,v,limitv)[m,n]=size(v);w=limitv*ones(m,n);p=zeros(n);nbox=0;fori=1:nforj=1:iifv(i)

3、入该箱子中”（FF算法）改为选择最佳的箱子(已装载物品大小和最大的－这个称为bestfit-BF最佳适应算法)，再计算一次上题。比较两次求解的结果。练习题4：背包问题：c=[10,5,15,7,6,18,3];w=[2,3,5,7,1,4,1];limitw=15;n=7;求最优解。练习题5：“超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm3,奖品i占用的空间为widm3,价值为vi元,具体的数据如下:vi={220,208,198,192,180,180,165,162,160,158,155,130,125,1

4、22,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1}wi={80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1}。模型的建立：设为

5、二进制变量，如果物品j被选中，则=1，否则，=0，如此可将本题转化为如下优化模型：max；s.t.模型的解决：对此优化问题，我们可以选用价值密度贪婪准则，从剩下的物品中选择可装入购物车的单位价值，最大的物品，即按非递增的次序装入物品，只要正被考虑的物品装的进就装入小车。其MATLAB编程代码如下：function[a1,b1]=sort1(n,a,b)%按单位价值排序[m,n]=size(a);d=zeros(m,n);fork=1:nd(k)=a(k)/b(k);end%单位价值forh=1:n-1forj=1:n-h%向后排序ifd(j)

6、

7、w(i)>clbreak%待放入包的物品重量大于包的重量,跳出循环elsex(i)=1;%x(i)为1时,物品i在包中cl=cl-w(i);p=p+1;%p记录放入背包物品的个数endendfunctionknapsack(n,limitw,w,v)totalc=0;totalw=0;[m,n]=size(w);%m是w的行数n是w的列数x=zeros(m,n);t=w;%记录原数组k=c;y=x;[p,c,w]=goodsinknapsack(n,limitw,v,w,x);%排序及计算装箱物品数forj=1:p%装包的p件物品fori=1

8、:n%原n件物品if(w(j)==t(i))&&(c(j)==k(i))%被选择的物品装箱y(i)=1;endendendyfori=1:ntotalc=total