不同重量小球装箱优化问题：寻求非暴力高效算法方案

现有若干不同重量的小球和多种箱型：

• 每个小球重量各不相同。
• 每种箱型设有min（最小容量）、max（最大容量）及使用时的penalty（惩罚值）。
• 每种箱型的数量无限。

如何将小球装入数量最少的箱子中，同时满足以下条件：

• 每个箱子内小球的总重量需处于其min与max容量范围内。
• 所用箱子的总penalty需最小化。
• 若存在多个解，需选择每个箱子内小球总重量最接近其max容量的方案。

例如，有5个重量分别为31、14、13、12、7的小球，以及3种箱型：

type│ min │ max │penalty
────┼─────┼─────┼───────
 A  │  11 │  20 │    1
 B  │  21 │  30 │    1
 C  │  31 │  40 │    5

可能的装箱组合如下：

boxTypes│ 31 │ 14 │ 13 │ 12 │  7 │ penalty
────────┼────┼────┼────┼────┼────┼─────────
   ABC  │ C  │ B  │ B  │ A  │ C  │    7
   BBC  │ C  │ B1 │ B2 │ B2 │ B1 │    7
    CC  │ C1 │ C2 │ C2 │ C2 │ C1 │   10
   ACC  │ C1 │ C2 │ C2 │ A  │ C2 │   11

还有许多未列出的组合，要么箱型集合相同，要么penalty过高。

注意有2种方案的总penalty相同，但结合第三个条件：

boxTypes │ box1 │ box2 │ box3 │            shortfall
─────────┼──────┼──────┼──────┼──────────────────────────────────
  ABC    │  12  │  27  │  38  │ (20-12) + (30-27) + (40-38) = 13
  BBC    │  21  │  25  │  31  │ (30-25) + (30-25) + (40-31) = 19

由于ABC组合的箱子填充率最高，因此被选中。

我目前通过递归生成小球的所有分组组合，再验证是否存在适配的箱型。

已通过以下方式优化性能：

• 提前终止：当分组重量超过最大容量（如示例中的40）时停止递归。
• 限制箱数：将箱数限制在2-3个（而非每个小球一个箱子）。

但该方案仍无法处理超过15个小球的场景。

是否存在优于暴力枚举的算法来解决此问题？

内容的提问来源于stack exchange，提问作者Uahnbu Tran