我有24张牌，8张红色，8张蓝色和8张黄色。
red |1|2|3|4|5|6|7|8|
yellow |1|2|3|4|5|6|7|8|
blue |1|2|3|4|5|6|7|8|
我可以拿三张牌（相同的号码，直牌，直牌），而每种牌的得分都不一样。
我的问题是，如何计算一个正在进行中的游戏的最大可能得分（找到最佳组），其中一些卡已经丢失。
例如：
red |1|2|3|4|5|6|7|8|
yellow |1|2|3| |5| |7|8|
blue |1|2| |4|5|6| |8|
三人组的得分是：
1-1-1 20
2-2-2 30
3-3-3 40
4-4-4 50
5-5-5 60
6-6-6 70
7-7-7 80
8-8-8 90
直线的得分是：
1-2-3 10
2-3-4 20
3-4-5 30
4-5-6 40
5-6-7 50
6-7-8 60
直冲得分是：
1-2-3 50
2-3-4 60
3-4-5 70
4-5-6 80
5-6-7 90
6-7-8 100
最佳答案
递归尝试每个组合的解决方案如下：
开始寻找红色8作为最高卡的组合：三种类型的r8-y8-b8，直冲r6-r7-r8，以及所有可能的直*6-*7-r8对于其中的每一个，从集合中移除卡片，并递归检查与黄色8、蓝色8、红色7、黄色7、蓝色7、红色6的组合…直到你检查了除了2和1以外的所有东西；然后添加三个同类的2-2-2和1-1-1（如果有的话）。在每个步骤中，检查哪个递归返回最大分数，并返回此最大值。
让我们看看在每个步骤中发生了什么假设我们正在寻找红色8的组合；我们有可用的卡，如：
red ...|6|7|8|
yellow ...|6| |8|
blue ...| |7|8|
首先，尽可能使用三种R8-Y8-B8。创建可用卡的副本，删除8，然后直接递归到7：
score = 90 + max_score(cards_copy, next = red 7)
（只有当当前卡为红色时，才应尝试使用三种方法，以避免重复解决方案。）
然后，如果可能，使用直冲R6-R7-R8。创建可用卡的副本，删除r6、r7和r8，并递归到黄色8：
score = 100 + max_score(cards_copy, next = yellow 8)
然后，使用包含红色8的所有可能的非齐平直线；在示例中，这些是r6-b7-r8、y6-r7-r8和y6-b7-r8（最多可以有9个）。对于其中的每一个，创建一个可用卡的副本，删除三个卡并递归到黄色8：
score = 60 + max_score(cards_copy, next = yellow 8)
最后，在不使用红色8的情况下递归：创建可用卡的副本，删除红色8并递归到黄色8：
score = max_score(cards_copy, next = yellow 8)
然后，计算这些选项中哪一个具有最大得分（加上其递归返回的得分），并返回该最大得分。
在JavaScript中的快速测试表明，对于一组完整的24张卡，该算法通过3000万次递归找到最大得分560，并且变得相当慢。然而，一旦3张高值卡被移除，递归次数就会降到100万次以下，大约需要1秒，而6张高值卡被移除后，递归次数就会降到20000次以下，并几乎立即返回。
对于几乎完整的集合，您可以预先计算最大分数，并且仅在一定数量的卡被移除之后才计算得分。无论如何，许多集合都是重复的；移除R6 R7 R8将导致与移除Y6 Y7 Y8相同的最大分数；移除R6 Y7 B8是删除B6 Y7 R8的副本。因此，首先将输入更改为规范版本，然后查找预先计算的分数。例如，对于所有已移除3张或6张卡片的集合，使用预先计算的分数需要存储45340个分数。
作为一个代码示例，下面是我用以下代码测试算法的javascript代码：
function clone(array) { // copy 2-dimensional array
var copy = [];
array.forEach(function(item) {copy.push(item.slice())});
return copy;
}
function max_score(cards, suit, rank) {
suit = suit || 0; rank = rank || 7; // start at red 8
var max = 0;
if (rank < 2) { // try 3-of-a-kind for rank 1 and 2
if (cards[0][0] && cards[1][0] && cards[2][0]) max += 20;
if (cards[0][1] && cards[1][1] && cards[2][1]) max += 30;
return max;
}
var next_rank = suit == 2 ? rank - 1: rank;
var next_suit = (suit + 1) % 3;
max = max_score(clone(cards), next_suit, next_rank); // try skipping this card
if (! cards[suit][rank]) return max;
if (suit == 0 && cards[1][rank] && cards[2][rank]) { // try 3-of-a-kind
var score = rank * 10 + 20 + max_score(clone(cards), 0, rank - 1);
if (score > max) max = score;
}
for (var i = 0; i < 3; i++) { // try all possible straights
if (! cards[i][rank - 2]) continue;
for (var j = 0; j < 3; j++) {
if (! cards[j][rank - 1]) continue;
var copy = clone(cards);
copy[j][rank - 1] = 0; copy[i][rank - 2] = 0;
var score = rank * 10 - 10 + max_score(copy, next_suit, next_rank);
if (i == suit && j == suit) score += 40; // straight is straight flush
if (score > max) max = score;
}
}
return max;
}
document.write(max_score([[1,1,1,1,1,0,1,1], [1,1,1,1,1,1,1,0], [1,1,1,0,1,1,1,1]]));加快算法速度的一个明显方法是使用24位模式而不是3x8位数组来表示卡；这样就不再需要克隆数组，而且大多数代码都变成了位操作。在JavaScript中，速度快了8倍：
function max_score(cards, suit, rank) {
suit = suit || 0; rank = rank || 7; // start at red 8
var max = 0;
if (rank < 2) { // try 3-of-a-kind for rank 1 and 2
if ((cards & 65793) == 65793) max += 20; // 65793 = rank 1 of all suits
if ((cards & 131586) == 131586) max += 30; // 131586 = rank 2 of all suits
return max;
}
var next_rank = suit == 2 ? rank - 1: rank;
var next_suit = (suit + 1) % 3;
var this_card = 1 << rank << suit * 8;
max = max_score(cards, next_suit, next_rank); // try skipping this card
if (! (cards & this_card)) return max;
if (suit == 0 && cards & this_card << 8 && cards & this_card << 16) { // try 3oaK
var score = rank * 10 + 20 + max_score(cards, 0, rank - 1);
if (score > max) max = score;
}
for (var i = 0; i < 3; i++) { // try all possible straights
var mid_card = 1 << rank - 1 << i * 8;
if (! (cards & mid_card)) continue;
for (var j = 0; j < 3; j++) {
var low_card = 1 << rank - 2 << j * 8;
if (! (cards & low_card)) continue;
var cards_copy = cards - mid_card - low_card;
var score = rank * 10 - 10 + max_score(cards_copy, next_suit, next_rank);
if (i == suit && j == suit) score += 40; // straight is straight flush
if (score > max) max = score;
}
}
return max;
}
document.write(max_score(parseInt("111101110111111111011111", 2)));
// B Y R
// 876543218765432187654321通过观察可以进一步提高几乎整套装备的速度，如果可以对当前等级的所有三套装备进行直冲，则这始终是最佳选择这大大减少了递归次数，因为可以一次跳过九张卡在尝试1级和2级的“同类3”后，应立即添加此检查：
if (suit == 0) { // try straight flush for all suits
var flush3 = 460551 << rank - 2; // 460551 = rank 1, 2 and 3 of all suits
if ((cards & flush3) == flush3) {
max = rank * 30 + 90;
if (rank > 2) max += max_score(cards - flush3, 0, rank - 3);
return max;
}
}
关于algorithm - 在2D数组中找到最佳组的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45686201/