matlab求贪婪算法-装箱问题的练习

利用matlab编程FFD算法完成装箱问题：设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。建立box_main.mfunction[box_count,b]=box_main(v)vmax=100;sort(v,'descend');n=length(v);b=zeros(1,n);fori=1:nb(i)=vmax;endbox_count=1;fori=1:nforj=1:box_countifv(i)=b(j)%可以放入b(j)=b(j)-v(i);break;else%不可放入时continue;endendifj==box_countbox_count=box_count+1;endendbox_count=box_count-1;end主程序为：v=[604535202020];[box_count,b]=box_main(v)结果：box_count=3b=51580100100100所以，使用的箱子数为3,使用的箱子的剩余空间为5，15，80。“超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm3,奖品i占用的空间为widm3,价值为vi元,具体的数据如下:vi={220,208,198,192,180,180,165,162,160,158,155,130,125,122,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}。解：模型建立：用价值密度贪婪准则的方法设x=v/w，对x做正向排序，依次选取商品。建立chaoshi.mfunction[item_count,y]=chaoshi(v,w,car)n=length(v);x=zeros(n,3);x(:,1)=v';x(:,2)=w';x(:,3)=v'./v';x=sortrows(x,-3);item_count=0;fori=1:nifcar=x(i,2)car=car-x(i,2);item_count=item_count+1;elsebreak;endendy=zeros(item_count,2);fori=1:item_county(i,1)=x(i,1);y(i,2)=x(i,2);endend主程序为：v=[220,208,198,192,180,180,165,162,160,158,155,130,125,122,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];w=[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];car=1000;[item_count,y]=chaoshi(v,w,car);y’；结果为：ans=Columns1through111585811595821181056965162902510222522323020205028Columns12through22101125155968816098562201921003240503230553520807038Columns23through261807712220870304882最大总价值为3095元，可装入体积为996