贪婪算法练习练习题1：考虑1、8、9、11这四种面值的硬币，要找出币值24的零钱，怎么找能使硬币数最少？利用matlab编程求解。解：设为二进制变量，如果硬币j被选中，则，=1，否则=0，则找硬币问题的数学模型如下：min；；用贪婪算法求解，其MATLAB程序如下：function[n,x]=payback(v,y,m)[m,n]=size(y);fori=1:nforj=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;fori=1:nforj=1:iifv(i)clbreak%待放入包的物品重量大于包的重量,跳出循环elsex(i)=1;%x(i)为1时,物品i在包中cl=cl-w(i);p=p+1;%p记录放入背包物品的个数endendfunctionknapsack(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);%排序及计算装箱物品数forj=1:p%装包的p件物品fori=1:n%原n件物品if(w(j)==t(i))&&(c(j)==k(i))%被选择的物品装箱y(i)=1;endendendyfori=1:ntotalc=totalc+k(i)*y(i);%背包的总价值ify(i)==1totalw=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=Columns1through161101010111101101Columns17through321011011111110100Columns33through480010100110000000Columns49through5000totalw=996totalc=3095结果分析：由运行结果可知，被选中的物品编号为向量y中的1，其所选物品总价值为3095，总体积为996；贪婪算法并不一定能得到最优解，但可以得到一个较好的解。
