找出求和为特定值的所有子集，然后选择这些子集中最有价值的组合

Question

我正在尝试创建一个简单的骰子游戏。为了计算分数，我必须找到所有总和为特定值的子集，然后选择最有价值的组合。所有数字只能拾取一次。可能最容易用一个例子来描述：

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。

我已经设法解决了"寻找可能的子集"部分，但我正在努力寻找找到的子集的最有价值的组合。有人能帮我吗？：(

Answer 1

既然您已经找到了组合，我将集中精力对它们进行分组。首先，我们需要确保我们知道两个组何时相等。

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

｛1,4｝等于｛4,1｝？

｛1,4｝不同于｛1,1,1,2｝

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

现在，让我们回到是否

｛1,4｝等于｛4,1｝？

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