algorithm - 装箱动态规划题

Question

您有 n1 件尺寸为 s1 的元素、n2 件尺寸为 s2 的元素和 n3 件尺寸为 s3 的元素。您希望将所有这些元素装入每个容量为 C 的箱子中，以使使用的箱子总数最少。

我们如何使用最少数量的 bin 实现解决方案？贪婪不一定有效。

Answer 1

这不是一个愚蠢的问题，IMO。

通常已知装箱是 NP 完全的。

但是你的情况，用固定数量的物体重量装箱是一个有趣的变体。

以下论文声称有一个多项式时间算法，其中包含 1 个最优值:http://linkinghub.elsevier.com/retrieve/pii/S0377221706004310当您允许 3 种不同尺寸时。 (警告:我只是按照摘要进行)。

所以我猜这个版本也是 NP-Hard，贪心算法可能不起作用。不太确定动态规划(bin packing 是强 NP-Complete)。

希望对您有所帮助。