algorithm - 找到总和为特定值的所有子集，然后选择这些子集的最有值(value)的组合

Question

我正在尝试创建一个简单的骰子游戏。要计算分数，我必须找到总和为特定值的所有子集，然后选择最有值(value)的组合。所有号码只能选一次。用一个例子可能最容易描述:

Values =  {1, 1, 1, 2, 4, 4}

Target value = 5

Possible subsets = {1, 1, 1, 2} and {1, 4}

现在可以选择:

{1, 1, 1, 2} (= worth 5)

或

{1, 4} {1, 4} (= worth 10)

所以在这个例子中，我希望算法返回 10 而不是 5。

我已经设法解决了“寻找可能的子集”部分，但我正在努力寻找已找到子集的最有值(value)的组合。谁能帮我？ :(

Answer 1

既然你已经找到了组合，我就专注于对它们进行分组。首先，我们需要确保我们知道两组何时相等。

{1,4} 等于 {1,4}

{1,4} 等于 {4,1} 吗？

{1,4} 不同于 {1,1,1,2}

因此，您需要确保您的程序可以进行适当的比较。为此，您需要生成一个组合的“签名”，即一个值(例如一个字符串)，因此只要您对两组是否相等感兴趣，就可以比较它们的签名。您将需要一个签名和数字的数据结构(映射)，它将存储所有出现的签名及其出现次数。每当你得到一个组合时，你将需要找出 map 是否包含给定的签名。如果是这样，请增加出现次数。如果不是，则将签名添加到 map 中，值为 1。找到所有组合后，在 map 中找到具有最大值的条目，这将是解决方案。

现在，让我们回到是否

{1,4} 等于 {4,1}？

如果两者相等，那么您需要在生成签名之前对组合的项目进行排序。如果两者不相等(这意味着我们正在处理变体)，那么您不需要对项目进行排序，只需以其原始形式生成签名即可。