物流装箱问题 -- 斜率法

异想时刻

由于要同时考虑箱子的承重和体积，那么为了尽可能同时达到和，我们可以优先考虑体重比最接近箱子体重比的物品。比如，若优先考虑将箱子装满，即体积维度，则在的范围内搜索，直到无满足条件，再考虑重量维度。

箱子的斜率
物品的斜率
所以它们都满足线性关系

注意，每装完一种物品后，需要重新计算箱子的斜率，直到箱子无法容纳其他物品为止。

举例说明

这里我们用一个例子来说明运算逻辑。

箱子

,

物品

物品	重量	体积	数量
A	2	2	3
B	3	2	5
C	4	5	8

那么，箱子及物品的斜率为：

Step 1, 在不超重的前提下，优先考虑A，装箱数量为
箱子的剩余重量和体积为和， 新的斜率为
Step 2, 类比Step 1, 优先考虑C，装箱数量为
箱子的剩余重量和体积为和, 新的斜率为
Step 3, 优先考虑B，装箱数量为
箱子的剩余重量和体积为和。无法容纳物品，结束。

最终可装箱A->3, B->2, C->2。

方法描述

上述例子是优先考虑箱子的承重，在实际装箱过程中，我们则是优先考虑体积。说白了就是在不超重的前提下，尽可能地多装物品。下面给出体积优先的算法步骤。

Step 1, 计算原始斜率
Step 2, 若找到最小且，则计算物品的装箱数量，更新物品i的数量，重新计算箱子承重和体积及斜率， 继续Step 2，否则，转Step 3
Step 3, 找到最大，计算物品的装箱数量，更新物品的数量，重新计算箱子承重和体积及斜率，转step 2
Step 4, 直到所有物品数量为0或箱子装满为止

伪代码

ki = wi/vi
sort ki from top to bottom and save the sorted index
boxes = new vector()
while sum{si}>0
	box = new int[N]
	while W>0 && V>0 && sorted_index.length>0
		K = W/V
		will_load = -1
		for i in sorted_index
			if K >= ki
				will_load = i
				break
		if will_load == -1
			will_load = sorted_index.back()
			num = min{floor(W/w[will_load], s[will_load]}
		else
			num = min{floor(V/v[will_load]), s[will_load]}
		if num <= 0
			break
		W -= num*w[will_load]
		V -= num*v[will_load]
		s[will_load] -= num
		box[will_load] = num
		// 已装箱的物品不再考虑
		sorted_index.remove(will_load)
	boxes.push_back(box)

结论

可以看出，相比于多重背包算法，此方法要简单很多，或许也实用的多。另外，从效率上说，此方法也更加高效。希望有更精妙的算法，欢迎探讨。