您有 n1 件尺寸为 s1 的元素、n2 件尺寸为 s2 的元素和 n3 件尺寸为 s3 的元素。您希望将所有这些元素装入每个容量为 C 的箱子中，以使使用的箱子总数最少。
我们如何使用最少数量的 bin 实现解决方案？贪婪不一定有效。
最佳答案
这不是一个愚蠢的问题，IMO。
通常已知装箱是 NP 完全的。
但是你的情况，用固定数量的物体重量装箱是一个有趣的变体。
以下论文声称有一个多项式时间算法，其中包含 1 个最优值:http://linkinghub.elsevier.com/retrieve/pii/S0377221706004310当您允许 3 种不同尺寸时。 (警告:我只是按照摘要进行)。
所以我猜这个版本也是 NP-Hard，贪心算法可能不起作用。不太确定动态规划(bin packing 是强 NP-Complete)。
希望对您有所帮助。
关于algorithm - 装箱动态规划题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5720299/