-5

我正在尝试检查玩家是否无法再移动，但我似乎无法弄清楚如何检查它。假设我有 5 个或更少的图块，每个图块的值在 1 到 3 之间。我想遍历瓷砖并检查是否有任何可能的组合加起来为 10。它不像检查总数那么简单，因为可能有 3 个瓷砖上有 3 个，一个有 2。我已经花了几个小时试图弄清楚这一点....

关于如何检查所有可能的组合的任何想法？我只需要看看一种组合是否可行。一旦找到一个，我就会打破循环以减少检查次数。

编辑：如果它有帮助，如果你下载它，你可以看看我在说什么。它的数字： 21 在 android 上。

游戏的目的是将牌添加到 21。因此，当用户减少到几张牌时，有时即使所有牌的总和超过 21，也无法获得 21 的组合，因为数字加起来并不完全一致21. 这造成了一个问题，因为我无法检查并告诉用户他们丢失了。

在检查它时，我什至不知道从哪里开始。我可以多次循环遍历所有的瓷砖，但事情是一个组合，可能是板上有很多瓷砖。所以我必须检查 3 的组合，然后是 4 ，然后是 5 等等，直到达到剩余的瓷砖数量。我很难准确地解释这一点

更正编辑以供将来参考：

对于我最初的问题如此模棱两可，我深表歉意。碰巧是我在这里问过的第一个问题......这是对问题和解决方案的更好描述。我决定保留以前的文字作为记录。

游戏有许多编号的瓷砖，我必须将它们添加到 21 才能删除。你不能超过 21。它必须是准确的。

我想要检查的是是否还有可以用来精确加起来 21 的瓷砖组合。基本的总和检查不起作用，因为您可能有 5 个 5 号牌并且超过 21 个，但无法再消除。

解决方案

正如@mellamokb 回答需要使用子集和递归一样。基本上，您循环遍历图块，并在每个图块上调用相同的函数两次。一个调用添加当前切片，另一个调用继续下一次迭代而不添加当前切片。如果有任何返回 true，则该函数为 true。基本上是二叉树。

代码

boolean validate(tiles, index, subtotal, total){
    if index >= tiles.length return false;
    if subtotal == total return true;
    return validate(tiles, index + 1, subtotal + tiles[index].number, total) || 
       validate(tiles, index + 1, subtotal, total);
}

调用它

validate(tiles, 0, 0, 21)

差不多就行了。

4

1 回答 1

4

这听起来像是子集和问题的变体。最简单的算法是 O(2^n)，例如，通过使用位标志迭代每个可能的子集组合。

for i = 0 to 2^n - 1
    set subtotal = 0
    for each bit in i
        if bit i is set, add ith element to subtotal
    check subtotal against desired total (i.e., 10)

或者，或者使用递归：

validate(set, index, subtotal, total)
    if index >= set.length return false;
    if subtotal == total return true;
    return validate(set, index + 1, subtotal + set[index], total) || 
           validate(set, index + 1, subtotal, total);

用法：

validate(set, 0, 0, 10);
于 2012-08-20T22:23:27.000 回答