algorithm - 集装箱配送问题

Question

问题是我有货物要发送给客户，这些货物必须装在集装箱中，每个集装箱只包含一个货物。我想确定将这些货物放入其中的最佳集装箱尺寸和每种尺寸的集装箱数量是多少？最大集装箱尺寸等于最大装运量。因此，我需要指定其他容器的大小，以最大限度地利用这些容器的空间。假设我有 50 批货物，我应该有 3 个集装箱尺寸。因此，解决方案应该是 50 个容器、三种容器尺寸以及每种尺寸的容器数量。

目标函数：

最大化容器的平均利用率

服从：

每个集装箱只有一次装运

最大集装箱尺寸等于最大装运量

预期的解决方案：

容器尺寸

每种尺寸的容器数量

标签： algorithm

Answer 1

有一个 O(k n²) 时间的动态程序，其中 n 是装运数量，k 是不同集装箱尺寸的数量。

让装运大小为 s ₁ ≤ s ₂ ≤ ... ≤ s _n。令 W(i, j) 为使用 i 个不同尺寸的容器包装货物 s ₁ , s ₂ , ... s _j的最小浪费空间。基本情况

W(1, j) = sum _{i∈{1,...,j}} (s _j − s _i )

希望清楚。对于 i > 1，递归

W(i, j) = min _{ℓ∈{1,...,j}} (W(i−1, ℓ) + sum _{i∈{ℓ+1,...,j}} (s _j − s _i ) )

说我们应该找到最大容器（大小为 s _j）和较小容器之间的最佳划分。

唯一的技巧是评估递归中的总和，我们应该向下迭代 ℓ 以便我们可以重用部分总和。

为了实际恢复最佳尺寸，我们记住每个 W(i, j) 的最小参数并从 W(n, k) 向后工作。