optimization - Bin Packing : Set amount on bins, 想要最小化最大 bin 重量

Question

给定 n 个无限容量的箱子，我想将 m 件元素装入其中(每个元素都有特定的重量)，同时最小化最重箱子的重量。

这不是传统的垃圾箱包装/背包问题，其中垃圾箱的容量有限，而您试图尽量减少使用的垃圾箱数量；我有一定数量的垃圾箱，并希望将它们全部使用，以使最重的垃圾箱的重量尽可能低。

这个问题有名字吗？我浏览了一些带有关键词的论文，但没有发现类似的。

干杯。

Answer 1

如果bins的数量是约束，而不是bins的容量，那么它不是binpacking，它是multiprocessor scheduling问题。

通常，您可以通过 LPT 算法来解决这个问题，结果非常好。不过需要优化，这就是乐趣所在。