这个算法面试题没有做出来，刷了那么久的题，面试死在这题上了

感觉就算是只发牌给一个人都要遍历所有情况，想不出别的解法。。会不会题目是要求统计黑杰克的次数？这样难度会正常一些（黑杰克是只能A+10/J/Q/K）

xujr 发表于 2017-5-17 19:09
感觉就算是只发牌给一个人都要遍历所有情况，想不出别的解法。。会不会题目是要求统计黑杰克的次数？这样难 ...

只发牌给一个人不需要遍历所有情况，只需要先找到最快组合成21点的发牌方式，然后再剩下的牌里重复这样的操作就能得到最优解。

qich 发表于 2017-5-17 19:56
只发牌给一个人不需要遍历所有情况，只需要先找到最快组合成21点的发牌方式，然后再剩下的牌里重复这样的 ...

感觉不行啊，比如A 4 5 3 9 A 10 10，先找最快组合21点的话就只有1组【A 4 5 3 9 A 10】10，其实可以组两组A【4 5 3 9】【A 10】10
也可能是我没理解

xujr 发表于 2017-5-17 20:06
感觉不行啊，比如A 4 5 3 9 A 10 10，先找最快组合21点的话就只有1组【A 4 5 3 9 A 10】10，其实可以组两 ...

这种情况下，最快得到21的就是【4 5 3 9】，因为9的位置显然比10要靠前。然后这算一轮结束，然后对剩下的A 10 10做同样的操作，就得到组合【A，10】，所以最优情况能得到2个21点。就是让得到21点时发的最后一张牌尽可能靠前。只要简单的写个迭代就能实现这个算法了。

所以我说把集满一次21点视作一轮，因为一轮结束时让剩下的牌尽可能的多，一定比剩下牌少的情况要好，因为剩下牌少的情况能在剩下的轮次得到的组合方式，剩下牌多的时候也肯定能实现。

xujr 发表于 2017-5-17 20:06
感觉不行啊，比如A 4 5 3 9 A 10 10，先找最快组合21点的话就只有1组【A 4 5 3 9 A 10】10，其实可以组两 ...

我语言表达能力实在捉急，简单的写了个代码：

int getN(vector<int>& cards, int begin, int n){
        //返回得到N点时最后一张牌的位置，如果失败返回55
        if(begin==cards.size())
                return 55;
        else if(cards[begin]==n)
                return begin;
        else if(cards[begin]==1 && n==11)
                return begin;
        else{
                if(cards[begin]>n)
                        return getN(cards,begin+1,n);
                else{
                        int index1 = getN(cards,begin+1,n-cards[begin]);
                        int index2 = getN(cards,begin+1,n);
                        int index3 = 55;
                        if(cards[begin]==1 && n>11)
                                index3 = getN(cards,begin+1,n-11);
                               
                        return min(index1,index2,index3);
                }
        }
}

运行这个代码就会得到我所说的一个轮次里的最优解，继续用你这个例子的话A 4 5 3 9 A 10 10，就会返回下标4，也就是第五位的9号卡片。

这样讲不知道你理解没_(:з」∠)_，实在不行就拷贝这个代码跑一下吧。

qich 发表于 2017-5-17 14:30
有个不甚成熟的做法：
（1）如果把这个问题简化一下，就是只发给一个人，那么发牌人就只有两种选择，也就 ...

诶嘿嘿，我想到证明方式了，这个解法应该是正确的，只不过如果出现了数个最优解，在第二步必须将所有的最优解情况进行尝试，否则最后不一定得到全局最优。

补充内容 (2017-5-18 11:06):
诶嘿嘿，卖了个蠢，然而卖蠢都没人吐槽我，伐开心，真正的解法我写下面了。

补充内容 (2017-5-18 11:15):
感觉我在玩单机论坛，孤单寂寞冷冷冷(ノへ￣、)

（1）如果把这个问题简化一下，就是只发给一个人，那么发牌人就只有两种选择，也就是{发牌，弃牌}。然后考虑这种情况下找到最优解，那么到一次集齐21点的情况（一个轮次），也就是满21的最后一张牌，牌的序号越前越好，这样我们可以找到一个轮次下的最优解。
       这样n个轮次之后，就会发完所有的牌，得到这个简化问题的最优解。设最最优解为OnePerson21（v），v为能发的牌。
（2）将问题扩展一下，就是将扑克牌发给n个人（n>1）。在这种情况下，也就是先将扑克牌分成n份（v1，v2，v3....），然后问题也就转化成令OnePerson21（vn）的和最大。写一个简单的递归（不是迭代，我之前笔误了）就搞定了，而原题即为n=4的情况。

解答完毕

update：
第二步直接递归可以解但是复杂度很高。实际上第一步和第二步都是动态规划的问题，可以用动态规划优化的方式进行优化得到复杂度更低的解法，但是除了这题，我已经两年没做过动规的题目了，所以这里就不瞎优化，权当抛砖引玉啦~

qich 发表于 2017-5-18 11:14
（1）如果把这个问题简化一下，就是只发给一个人，那么发牌人就只有两种选择，也就是{发牌，弃牌}。然后考 ...

一路在潜水。。。这个解法是对的，但是复杂度有点高。简化问题是一个二维DP，复杂度是21*v， 然后要考虑n=4的情况就要遍历O(v^4)种组合，不知道有没有更巧妙的办法。但是我想说你这个解法过面试肯定是没问题了吧，反正我是短时间内想不到。

qich 发表于 2017-5-18 11:14
（1）如果把这个问题简化一下，就是只发给一个人，那么发牌人就只有两种选择，也就是{发牌，弃牌}。然后考 ...

把52张牌分给4个人，共有C(52, 4)种分法，所以按层主你的这个解法需要遍历这每种分法的组合喽？对给定的一个分法，可以分解为4个单人问题来解。
Update :
C(52, 4)是错的