algorithm - 基于所选容器的运费计算

Question

我们正在为在线商店(市场)构建运输 API，以根据可以容纳订单上所有元素的最佳容器计算运输价格。
我们有 3 种类型的容器:

自行车尺寸为 10x10x10，运费 = 50 美元

货车尺寸为 50x120x100，运费 = 150 美元

尺寸为 300x500x1000 的大货车，运费 = 350 美元

市场应提供订单中每件商品的尺寸(高度、长度和宽度)。

我需要一个算法来找到每个订单应该使用哪个容器。
请注意，容器只能处理一个订单，但该订单可能有多个 item 。

Answer 1

这是https://en.wikipedia.org/wiki/Bin_packing_problem它是NP完全的。存在许多近似算法，其中一些在实践中相当快。

如果您只需要一个快速而肮脏的近似值，请将您的元素从最大尺寸总和到最小尺寸排序，并尝试将它们贪婪地包装在最小的盒子中。