贪婪算法装箱问题等练习.doc

贪婪算法练习练习题1：考虑1、8、9、11这四种面值的硬币，要找出币值24的零钱，怎么找能使硬币数最少？ 利用matlab编程求解。解：设为二进制变量，如果硬币j被选中，则，=1，否则=0，则找硬币问题的数学模型如下：min ；用贪婪算法求解，其MATLAB程序如下：function n,x=payback(v,y,m)m,n=size(y);for i=1:nfor j=1:n 练习题2：利用matlab编程FFD算法完成下题：设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。function nbox,p=sjy(n,v,limitv)m,n=size(v);w=limitv*ones(m,n);p=zeros(n);nbox=0;for i=1:n for j=1:i if v(i)w(j) w(j)=w(j)-v(i);p(i,j)=1;break; else continue; end w(j+1)=w(j+1)-v(i);p(i,j+1)=1; nbox=nbox+1; endend运行结果：p = 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0练习题3：如果把选择策略从“选出一个下标最小的箱子并把物品ai放入该箱子中”（FF算法）改为选择最佳的箱子(已装载物品大小和最大的这个称为best fit-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占用的空间为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。模型的建立：设为二进制变量，如果物品j被选中，则=1，否则，=0，如此可将本题转化为如下优化模型：max ；s.t. 模型的解决：对此优化问题，我们可以选用价值密度贪婪准则，从剩下的物品中选择可装入购物车的单位价值，最大的物品，即按非递增的次序装入物品，只要正被考虑的物品装的进就装入小车。其MATLAB编程代码如下：function a1,b1=sort1(n,a,b)%按单位价值排序m,n=size(a);d=zeros(m,n);for k=1:n d(k)=a(k)/b(k);end%单位价值for h=1:n-1 for j=1:n-h%向后排序 if d(j)cl break%待放入包的物品重量大于包的重量,跳出循环 else x(i)=1;%x(i)为1时,物品i在包中 cl=cl-w(i); p=p+1;%p记录放入背包物品的个数 endendfunction knapsack(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);%排序及计算装箱物品数for j=1:p%装包的p件物品 for i=1:n%原n件物品 if (w(j)=t(i)&(c(j)=k(i)%被选择的物品装箱 y(i)=1; end endend yfor i=1:n totalc=totalc+k(i)*y(i);%背包的总价值 if y(i)=1 totalw=totalw+t(i);%背包所装载总体积 endendtotalwtotalcv=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;limitw=1000;n=50;knapsack(n,limitw,w,v)；运行结果为：y = Columns 1 through 16 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1 Columns 17 through 32 1 0 1 1 0 1 1 1 1 1 1 1 0 1 0 0 Columns 33 through 48 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0