作业解答
练习题2 利用matlab编程FFD算法完成下题：
设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。
解答一：
function [num,s] = BinPackingFFD(w,capacity)
%一维装箱问题的FFD（降序首次适应）算法求解:先将物体按长度从大到小排序, %然后按FF算法对物体装箱
%输入参数w为物品体积，capacity为箱子容量
%输出参数num为所用箱子个数，s为元胞数组，表示装箱方案，s{i}为第i个箱子所装 %物品体积数组
%例w = [60,45,35,20,20,20]; capacity = 100; % num=3,s={[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) < bin(j)
bin(j) = bin(j) - w(i); s{j} = [s{j},i]; if j == num + 1 num = num + 1; end break; end end end
s = s(1:num);
解答二： clear; clc; V=100;
v=[60 45 35 20 20 20]; n=length(v); v=fliplr(sort(v)); box_count=1; x=zeros(n,n);
V_Left=100; for i=1:n
if v(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(x(i,:)==1);
fprintf('第%d个物品放在第%d个容器\\n',i,temp) end
output:
第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(j<=box_count) if x(i)>box(j) j=j+1; continue; else
box(j)=box(j)-x(i); E(i)=j; break; end end
if j>box_count
box_count=box_count+1;
box(box_count)=box(box_count)-x(i); E(i)=j; end end
disp(E);
在命令窗口输入：
>> x=[60,45,35,20,20,20]; >> FFD(x)
1 2 1 2 2 3 ans = 3
练习题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}。
问如何装车才能总价值最大。 解答：
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, 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