内容发布更新时间 : 2024/12/23 13:05:27星期一 下面是文章的全部内容请认真阅读。

作业解答

练习题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