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

利用matlab编程FFD算法完成装箱问题：设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100 个单位体积。建立box_mainmfunctionbox_count,b=box_main(v)vmax=100;sort(v,'descend'); n=length(v);b=zeros(1,n);for i=1:nb(i)=vmax;end box_count=1;for i=1:nfor j=1:box_countif v(i)<=b(j) %可以放入 主程序为： v=60 45 35 20 20 20;box_count,b=box_main(v)b(j)=b(j)-v(i);break;else %不可放入时continue;endendif j=box_countbox_count=box_count+1; endendbox_count=box_count-1;end结果：100 10015 ，80。box_count =3 b =5 15 80 100所以，使用的箱子数为 3, 使用的箱子的剩余空间为 5“超市大赢家”提供了 50种商品作为奖品供中奖顾客选择，车的容量为100Odm3 ,奖品i 占用的空间为wi dm3，价值为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, 1wi = 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做正向排序，依次选取商品。建立 chaoshimfunction if car>=x(i,2)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;for i=1:ncar=car-x(i,2);item_count=item_count+1;elsebreak;endendy=zeros(item_count,2);for i=1:item_county(i,1)=x(i,1);y(i,2)=x(i,2); end end主程序为：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 =Columns 1 through 111585811595821181056965162902510222522323020205028Columns 12 through 22101 125 1559688160985622019210032 40 503230553520807038Columns 23 through 2618077 122 2087030 48 82最大总价值为3095元，可装入体积为996