扑克牌最优组合算法题（动态规划+备忘录+快排）

GitHub：github.com/bllon/Data-structure-an...
题目如下

题目：
设一副包含点数从A到K,四种花色的52张牌, 将 三张及以上同点数不同花色的牌组 或者三张以及上的同花顺称为 `组合`,
求出给定一副20张以内的牌中,所能形成的最优的组合列表(最优即组合点数累加最大)
代码要运行正确而且要做输入处理，输出格式要按要求输出

实现代码：使用nodejs运行的，版本16.8.0

const { exit } = require('process')
var shuffle = require('shuffle-array')

//定义54张牌
color = ['红心','方块','梅花','黑桃']
num = ['1','2','3','4','5','6','7','8','9','10','11','12','13']
cards = []
cards_num = 20
// colors = []

//相同点数的牌
tong = []
//顺子
shunzi = []

//一副牌
for (i of color) {
    for (el of num) {
        cards.push(i + el)
    }       
}

console.log("初始化扑克牌, 共 " + cards.length + " 张")
console.log("打乱牌")
shuffle(cards)

console.log("取" + cards_num + "张")
cards = cards.slice(0,cards_num)
// console.log(cards)
cards = kuaipai(cards)
console.log(cards)

tong = calTong(cards)
console.log("大小相同的牌")
console.log(tong)

shunzi = calShunZi(cards)
console.log("所有顺子")
console.log(shunzi)

maxComb()

//快速排序
function kuaipai(cards)
{
    if (cards.length <= 1) {
        return cards
    }

    var left = [] , right = []
    var cards0 = parseInt(cards[0].substr(2))
    for (i=1;i<cards.length;i++) {
        if (parseInt(cards[i].substr(2)) < cards0) {
            left.push(cards[i])
        } else {
            right.push(cards[i])
        }
    }
    left = kuaipai(left)
    right = kuaipai(right)
    left.push(cards[0])
    return left.concat(right)
}

//计算相同牌
function calTong(cards)
{
    data = []
    for (i=0;i<cards.length;i++) {
        let j = parseInt(cards[i].substr(2))
        if (data[j] == undefined) {
            data[j] = []
        }
        data[j].push(cards[i])
    }

    tong = []
    for (item of data) {
        if (item &amp;&amp; item.length >= 3) {
            tong.push(item)
        }
    }
    return tong
}

//计算顺子
function calShunZi(cards)
{
    //找到所有长度大于等于3的同花顺
    data = []
    i = 0
    j = 1
    len = 1
    color = cards[i].substr(0, 2)
    num = parseInt(cards[i].substr(2))
    cur = [cards[i]]
    while (i < cards.length)
    {
        //花色相同且值连续
        if (cards[j].substr(0, 2) == color &amp;&amp; (parseInt(cards[j].substr(2)) - num) == len) {
            cur.push(cards[j])
            j++
            len++
            if (len >= 3) {
                //记录
                data.push(Object.assign([], cur))
            }
        } else if ((parseInt(cards[j].substr(2)) - num) > len) {
            //值发生跳跃改变i指针
            i++
            len = 1
            color = cards[i].substr(0, 2)
            num = parseInt(cards[i].substr(2))
            j = i + 1
            cur = [cards[i]]
        } else {
            j++
        }

        if (j == cards.length) {
            i++
            j = i + 1
            cur = [cards[i]]
            if (j >= cards.length) {
                break
            }
            len = 1
            color = cards[i].substr(0, 2)
            num = parseInt(cards[i].substr(2))
        }
    }

    return data
}

//是否交集
function jiaoji(a, b)
{
    for (i of a) {
        if (b.includes(i)) {
            return true
        }
    }
    return false
}

//计算最优组合
function maxComb()
{
    var zuhe = shunzi

    //列出所有情况
    for (t of tong) {
        zuhe.push(t)
        if (t.length > 3) { //4张相同牌对应四种情况
            for(let i=0;i<4;i++) {
                let tmp = [];
                for(let j=0;j<4;j++) {
                    if (j != i) {
                        tmp.push(t[j])
                    }
                }
                zuhe.push(tmp)
            }
        }
    }

    console.log("最后的组合")
    console.log(zuhe)

    //循环计算
    let i = 0
    data = []
    max_num = 0;
    good_zuhe = [];
    beiwang = []
    // numd = 0
    while (i < zuhe.length)
    {
        let result = getZuHe([i], zuhe)
        let cur_num = 0;
        for (j of result) {
            for (k of zuhe[j]) {
                cur_num += parseInt(k.substr(2))
            }
        }
        if (cur_num > max_num) {
            max_num = cur_num
            good_zuhe = result
        }
        i++
    }

    // console.log("进入函数" + numd + "次")
    console.log("最优组合是", good_zuhe, "大小为 " + max_num)
}

//递归选组合
//带备忘录
function getZuHe(choiced, data)
{
    // numd++
    let cur = []
    for (choice of choiced) {
        cur = cur.concat(data[choice])
    }
    let i = 0
    while(i < data.length) {
        if (choiced.indexOf(i) != -1) {
            i++
            continue
        }
        if (jiaoji(cur, data[i]) == false) {
            if (beiwang.indexOf(kuaipai_num(choiced.concat([i])).join(',')) >= 0) {
                i++
                continue;
            }
            return getZuHe(choiced.concat([i]), data)
        }
        i++
    }

    //排序后放入备忘录
    beiwang.push(kuaipai_num(choiced).join(','))
    return choiced
}

//快排数字
function kuaipai_num(arr)
{
    if (arr.length <= 1) {
        return arr
    }

    var left = [] , right = []
    var arr0 = arr[0]
    for (i=1;i<arr.length;i++) {
        if (arr[i] < arr0) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    left = kuaipai_num(left)
    right = kuaipai_num(right)
    left.push(arr[0])
    return left.concat(right)
}

最终运行结果如下：

有兴趣的小伙伴可以给出更好的建议和方法

​

本作品采用《CC 协议》，转载必须注明作者和本文链接