贪婪算法-装箱问题等练习.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；贪婪算法并不一定能得到最优解，但可以得到一个较好的解。