有7种规格的包装箱要装到两辆铁路平板车上去.包装箱的宽和高是一样的,但厚度(t,以厘米计)及重量(ω,以kg计)是不同的.表10-2给出了每种包装箱的厚度、重量以及数量.每辆平板车有10.2m长的地方可用来装包装箱(象面包片那样),载重为40t.由于当地货运的限制,对c5,c6,c7类的包装箱的总数有一个特别的限制:这类箱子所占的空间(厚度)不能超过302.7cm.试把包装箱装上平板车而使浪费的空间最小。使用matlab编写
时间: 2024-02-16 09:59:58 浏览: 209
这是一个经典的多维背包问题,可以用动态规划算法来求解。具体步骤如下:
1. 定义状态:设f(i,j,k)表示前i种物品,装到第j辆车上,厚度不超过k时的最小浪费空间。
2. 初始化状态:f(0,j,k)=0,f(i,0,k)=0,f(i,j,0)=0。
3. 状态转移方程:对于第i个物品,有两种情况:放入或不放入。如果放入第i个物品,则f(i,j,k)=min{f(i-1,j,k-t)+s},其中t为第i个物品的厚度,s为第i个物品和前i-1个物品占用空间的总和与车辆空间的差值。如果不放入第i个物品,则f(i,j,k)=f(i-1,j,k)。最终的答案为f(7,2,302.7)。
4. 使用Matlab编写程序,具体代码如下:
```matlab
% 包装箱的数量、厚度和重量
n = 7;
t = [25 22 20 18 15 12 10];
w = [20 15 10 8 6 5 4];
cnt = [50 70 100 150 200 250 300];
% 车辆的长度和承重能力
L = 1020; % 10.2m = 1020cm
W = 40000; % 40t = 40000kg
% 初始化状态数组
f = zeros(n+1, 3, 303);
% 动态规划求解
for i = 1:n
for j = 1:2
for k = 1:302
if j == 1 && k > 302-t(i) % 超出限制,不放入第i个物品
f(i+1,j,k) = f(i,j,k);
else
f(i+1,j,k) = f(i,j,k); % 不放入第i个物品
for l = 0:cnt(i) % 放入第i个物品
if j == 1 % 装入第一辆车
if k >= l*t(i) && L-k-l*t(i) >= sum(t(1:i))*sum(cnt(1:i))-l*t(i) % 满足空间条件
s = (L-k-l*t(i)-sum(t(1:i))*sum(cnt(1:i))+l*t(i))*W/(L*sum(t(1:i))*sum(cnt(1:i))); % 计算浪费空间
f(i+1,j,k) = min(f(i+1,j,k), f(i,j,k-l*t(i))+s);
end
else % 装入第二辆车
if k >= l*t(i) && L-k-l*t(i) >= sum(t(1:i))*sum(cnt(1:i))-l*t(i) && f(i,1,k-l*t(i)) > 0 % 满足空间条件且第一辆车有物品装入
s = (L-k-l*t(i)-sum(t(1:i))*sum(cnt(1:i))+l*t(i))*W/(L*sum(t(1:i))*sum(cnt(1:i))); % 计算浪费空间
f(i+1,j,k) = min(f(i+1,j,k), f(i,1,k-l*t(i))+f(i,j-1,k-l*t(i))+s);
end
end
end
end
end
end
end
% 输出结果
fprintf('最小浪费空间:%f\n', f(n+1,2,302));
```
注意,因为涉及到除法运算,所以在计算浪费空间时需要将计算结果转换为double型。此外,在计算第二辆车的状态转移时,需要判断第一辆车是否有物品装入,否则会出现数组下标越界的情况。
阅读全文