贪婪算法-装箱问题等练习.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:n for 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; end end 运行结果： 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, 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}。 模型的建立： 设为二进制变量，如果物品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)<d(j+1) t1=a(j);a(j)=a(j+1);a(j+1)=t1; t2=b(j);b(j)=b(j+1);b(j+1)=t2; t3=d(j);d(j)=d(j+1);d(j+1)=t3;% end end end a1=a; b1=b; function [p,c,w]=goodsinknapsack(n,limitw,v,w,x)%计算背包中物品数 cl=limitw;%cl为背包剩余可装载重量 p=0; [m,z]=size(c); x=zeros(m,z); [v,t]=sort1(n,c,w);%物品按单位价值排序 c=v;w=t; for i=1:n if w(i)>cl break%待放入包的物品重量大于包的重量,跳出循环 else x(i)=1;%x(i)为1时,物品i在包中 cl=cl-w(i); p=p+1;%p记录放入背包物品的个数 end end function 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 end end y for i=1:n totalc=totalc+k(i)*y(i);%背包的总价值 if y(i)==1 totalw=totalw+t(i);%背包所装载总体积 end end totalw totalc 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]; 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 0 Columns 49 through 50 0 0 totalw = 996 totalc = 3095 结果分析：由运行结果可知，被选中的物品编号为向量y中的1，其所选物品总价值为3095，总体积为996；贪婪算法并不一定能得到最优解，但可以得到一个较好的解。