c# - 根据简单规则对项目进行分组的算法

Question

我需要一些帮助来找到解决问题的好算法，但我什至不知道如何抽象这个问题，所以我会把这个问题写成我想要的例子。

假设我有一个包含 2 种类型(A 和 B)的项目列表，它们都有一个值。该列表如下所示:

1. A1 : 10
2. B1 : 11
3. A2 : 9
4. B2:6
5. B3 : 4

我的问题是我想根据以下规则尽可能多地分组项目:

• 必须至少有 1 个 A 项和 1 个 B 项
• 每组值的总和必须至少为20

算法的输出应该是:

找到 2 个组:

• 第 1 组包含 A1、B2 和 B3
• 第 2 组包含 A2 和 B1

问题的参数可能会有所不同:

• 当然是这个列表本身(项目数、值、...)
• 项目类型的数量(从 1 到很多)
• 每种类型所需的元素数量(我可能至少需要 A 中的 2 件元素和 B 中的 3 件元素)
• 所需的最低金额总和

我几乎可以肯定存在这样的算法，这让我想到了背包问题，但实际上我什至不知道要搜索什么。

---

更新:这是我为解决这个问题而制定的算法，以帮助您更好地理解我的需求。

---

算法一

该算法只是按顺序提取所需的项目，以达到每种类型的所需项目数并达到最小总和。

1. 取 A 类的第一个可用项
2. 取第一个可用的B类元素
3. 如有必要，可以拿更多的任何类型的元素以达到总数 20
4. 如果达到所有要求的项目和总和，将项目标记为不可用并返回第一组
5. 循环直到不能再组为止

此算法取决于列表的顺序并返回单个组:

• 第 1 组包含 A1 和 B1

速度非常快，但没有给我想要的结果。

---

算法2

该算法计算原始列表的所有可能排序并对所有可能性执行算法 1。

然后它从结果中取出最大组数并返回具有该组数的第一种可能性。

输出是我所期望的:

找到 2 个组:

• 第 1 组包含 A1、B2 和 B3
• 第 2 组包含 A2 和 B1

问题在于它具有指数复杂度，它在 5 个项目(120 种可能性)时速度很快，但在 10 个(3628800 种可能性)时速度较慢。

---

我需要一种算法来从算法 2 中获取结果，但速度更快，我需要一种启发式方法，但是...如何？

Answer 1

它可以很容易地通过数学约束求解器求解:

让我们使用以下术语:

• @A = 类别 A 的项目数
• @B = 类别 B 的项目数
• n = min(@A, @B)

为了得到一个有效的解，下面的等式必须成立:

• G_j 为 0 或 G_j 大于 20
• min(α_j_0 ... α_j_@A ... β_j_0 ... β_j_@B) 为 0 或 1
• sum(α_0_0 ... α_0_n) 为 1(每个 A 使用一次)
• sum(β_0_0 ... β_0_n) 为 1(每个 B 使用一次)

然后我们简单地最大化

T = i = 0 到 n of 2 ^ G_i - 1 的总和

这将为每个空组添加一个 0，并为每个非空组添加一个更大的值。