algorithm - 背包或类似元素，没有值(value)，但对哪些元素可以分配到哪里有限制？

Question

假设我有一些重量，我需要将它们分散到有限数量的背包中，以便每个背包的重量分布尽可能均匀。问题是不同的权重只能放入第一个 包，其中每个值为 每个重量都不同。

例如，一个重物可能最多只能插入第 4 个袋子，即第 1 到 4 个袋子。另一个可能有最多 5 个的限制。如前所述，目标是尝试均匀分布在所有袋子中, 行李件数由最高限重的重量决定。

这个问题有名称吗？有哪些算法？

编辑:为了帮助形象化，假设我有 4 个权重:

+----------+--------+-----------+
| Weight # | Weight | Bag Limit |
+----------+--------+-----------+
|        1 |      2 |         2 |
|        2 |      3 |         3 |
|        3 |      1 |         1 |
|        4 |      2 |         4 |
+----------+--------+-----------+

问题的解决方案可能是这样的

| 1 |  |   |  |   |  |   |
| 2 |  | 3 |  | 2 |  |   |
|___|  |___|  |___|  |___|

Bag 1  Bag 2  Bag 3  Bag 4

砝码 3 和 1 放入袋 1

重量 2 被放入袋 2

重量 4 被放入袋 3

这里，负载尽可能均匀地分布，问题就解决了(虽然可能不是最优的，因为我在脑海中这样做)

希望这可以澄清我要解决的问题。

Answer 1

我将这个问题描述为带有边约束的装箱问题——很多 NP 难问题都没有好名字，因为它们太多了。我希望基于 LP 的可变大小垃圾箱打包方法将问题分解为 (1) 整个垃圾箱的打包问题 (2) 垃圾箱内的背包问题，以生成候选垃圾箱，以便合理地进行处理。