贪婪算法-装箱问题等练习

1、贪婪算法练习练习题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

2、)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放入该箱子中”

3、（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

4、, 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

5、, 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:

6、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%

7、原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,

8、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