《图论习题及答案.doc》由会员分享，可在线阅读，更多相关《图论习题及答案.doc（24页珍藏版）》请在金锄头文库上搜索。
1、作业解答练习题2 利用matlab编程FFD算法完成下题：设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。解答一：function num,s = BinPackingFFD(w,capacity)%一维装箱问题的FFD（降序首次适应）算法求解:先将物体按长度从大到小排序,%然后按FF算法对物体装箱%输入参数w为物品体积，capacity为箱子容量%输出参数num为所用箱子个数，s为元胞数组，表示装箱方案，si为第i个箱子所装%物品体积数组%例w = 60,45,35,20,20,20; capacity = 100;% num=3,s
2、=1,3,2,4,5,6;w = sort(w,descend);n = length(w);s = cell(1,n);bin = capacity * ones(1,n);num = 1;for i = 1:n for j = 1:num + 1 if w(i) =max(V_Left) box_count=box_count+1; x(i,box_count)=1; V_Left=V_Left V-v(i); else j=1; while(v(i)V_Left(j) j=j+1; end x(i,j)=1; V_Left(j)=V_Left(j)-v(i); end temp=find
3、(x(i,:)=1); fprintf(第%d个物品放在第%d个容器n,i,temp)endoutput:第1个物品放在第1个容器第2个物品放在第2个容器第3个物品放在第1个容器第4个物品放在第2个容器第5个物品放在第2个容器第6个物品放在第3个容器解答三：function box_count=FFD(x)%降序首次适应算法v=100;x=fliplr(sort(x);%v=input(请输入箱子的容积:);n=length(x);I=ones(n);E=zeros(1,n);box=v*I;box_count=0;for i=1:n j=1; while(jbox(j) j=j+1; con
4、tinue; else box(j)=box(j)-x(i); E(i)=j; break; end end if jbox_count box_count=box_count+1; box(box_count)=box(box_count)-x(i); E(i)=j; endenddisp(E);在命令窗口输入： x=60,45,35,20,20,20; FFD(x) 1 2 1 2 2 3ans = 3练习题5 “超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm3 , 奖品i占用的空间为wi dm3 ,价值为vi 元, 具体的数据如下:vi = 220, 208,
5、 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,
6、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。问如何装车才能总价值最大。解答：clear;clc;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,
7、 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;totalw=1000;limitw=1000;n=length(w);for i=1:n f(1,i)=v(i)/w(i)
8、; f(2,i)=w(i); f(3,i)=i;endfor i=1:(n-1) for j=(i+1):n if f(1,i)f(1,j) t=f(1,i); f(1,i)=f(1,j); f(1,j)=t; t=f(2,i); f(2,i)=f(2,j); f(2,j)=t; t=f(3,i); f(3,i)=f(3,j); f(3,j)=t; end endendtotalv=0;a=;for i=1:n if f(2,i)=limitw a=a,f(3,i); %disp(f(3,i); limitw=limitw-f(2,i); totalv=totalv+f(1,i)*f(2,i)
9、; endendatotalvtotalw=totalw-limitw结果a = Columns 1 through 21 10 40 17 25 28 16 19 35 37 8 26 20 13 11 24 27 9 23 41 1 4 Columns 22 through 27 22 6 30 14 2 47totalv = 3103totalw = 1000练习题8 对最后一个求有向圈的示例用matlab程序实现。解答：H= 0 1 0 0 0; 0 0 0 1 1; 1 1 1 0 0; 0 0 1 0 1; 0 1 0 0 0;n=size(H,1);%顶点个数p=zeros(1,
10、n);%存储搜索过的顶点X=zeros(n,n);%用来设置禁止矩阵，往回返的时候设置此路已被搜索k=1;p(1)=1;%第一个点作为初始点开始搜索while p(1)=n %每个顶点都作为初始点搜索包含p(1)的有向圈， i=p(1)+1;%当前点k往后搜索时都是从p(1)+1开始，从而也可以搜索下标小于k的点while in %k点往后的所有点都被搜索 if H(p(k),p(1)=1%有圈，每次搜索的都是包含初始点的圈 disp(p(1:k);%输出圈 end %不管有没有圈，此时k点要往回返 if k1%路径上不止出发点 for j=1:n X(p(k),j)=0;%取消以前的限制通行 end X(p(k-1),p(k)=1;%增加此路已搜索 p(k)=0;%撤销路径上的k点 k=k-1;%返回上一个点作为当前点 else %返回到出发点了 p(1)=p(1)+1; %换下一个出发点（初始点） end endend运行结果：1 2 4 3 2 4 5 2 4 3 2 5 3练习题9 选址问题 现准备在7个居民点中设置一银行，路线与距离如下图，问设在哪个点，可使最大服务距离最小？若设两个点呢？解答：第一步：function D,R=floyd(A)%用floyd算法实现求任意两点之间的
