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

参加了一个面试，一道算法题是这样的，我没有做出来，大家帮我看看，我觉得好难。

题目根据回忆是这样的：

发牌人手上有52张扑克牌，在一个初始化好了的数组里面（已经知道牌的点数，J,Q,K价值是 10，A 比较特殊可以 价值 1，也可以价值 11），发牌人自己能看见数组里牌的点数和顺序，另外有四个人，发牌人可以把数组里面的牌一张一张的按照数组里的顺序发给四个人中的任何一个（条件是这个人拿了这张牌后，他手中的牌点数之和小于等于21），牌必须按照初始化好的数组里面的顺序发，发牌人想把一张牌发给4个人中的谁就发给谁。发牌人也可以选择丢掉这张牌，不发给任何人。 如果当前4个人，拿了这张牌，手上点数都大于21，那么发牌人必须把这张牌扔掉。任何人，手上的牌，点数之和达到21点后，得把手上的所有牌扔掉，算成功达到21点一次，他又可以开始接牌。请给发牌人设计一种算法（每张牌发给谁，还是丢掉），让4个人产生的21点成功次数总和最多。 不涉及任何概率的问题，因为数组里的牌是已知的。

输入：数组，52个元素代表52张牌

要求输出：
（1）        整数的一维数组，52个元素，0代表丢掉了，1代表给了第一个人，2代表给了第二个人，3代表给了第三个人，4代表给了第四个人
（2）        总共产生了几次21点


面试的时候，死在这道题上面，其他的题目都做对了，感觉这是离offer最近的一次。郁闷死了！

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

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

conlor 发表于 2017-5-22 11:46
谢谢你提供算法的解。假如牌的序列如下，你能算一下最后的解吗？
String cards="5,10,8,5,2,3,J,Q,9,A,K ...

看了一下楼主的求解过程，感觉楼主是看到了最开始的那个解法，那种解法是错误的，第二步用的是贪心，会陷入局部最优，没办法得到全局最优解。正解在第18垅：
（1）如果把这个问题简化一下，就是只发给一个人，那么发牌人就只有两种选择，也就是{发牌，弃牌}。然后考虑这种情况下找到最优解，那么到一次集齐21点的情况（一个轮次），也就是满21的最后一张牌，牌的序号越前越好，这样我们可以找到一个轮次下的最优解。这样n个轮次之后，就会发完所有的牌，得到这个简化问题的最优解。设最最优解为OnePerson21（v），v为能发的牌。
（2）将问题扩展一下，就是将扑克牌发给n个人（n>1）。在这种情况下，也就是先将扑克牌分成n份（v1，v2，v3....），然后问题也就转化成令OnePerson21（vn）的和最大，而原题即为n=4的情况。

当然这个算法效率是非常低的，所以必须要剪枝、记录中间值等方式来减少时间复杂度。

下面给出的是伪代码（是的我就是懒），因为实在太复杂了我手动计算是算不动的，我就不手动计算一次了（电脑应该也跑不出来）：

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);
                }
        }
}
int get21(vector<int>& v){
        int begin = 0;
        int num = -1;
        do{
                num++;
                begin = getN(v,begin,21);
        }while(begin<55);
        return num;
}
int OPT(map<int,int>& m, int i){
   if(i>=m.size){
                   //分完四组牌
                   v1 = {x|map[x]==1};//所有分给第一个人的带序扑克牌
                   v2 = {x|map[x]==2};
                   v3 = {x|map[x]==3};
                   v4 = {x|map[x]==4};
                   return get21(v1)+get21(v2)+get21(v3)+get21(v4);
   }else{
                   int num[4];
                   for(int t=0; t<4; t++){
                           map = t+1;
                           num[t][i] = OPT(m,i+1);
                   }
                   return max(num[0],num[1],num[2],num[3]);
   }
}

注：OPT部分如果进行优化将重复出现的情况去除，可以将需要遍历的情况从4^52变成C(52,4)即270725，也一共需要进行27万次。（简单的优化过之后电脑应该勉强能够跑出来，如果追求更快的速度可以进一步优化
优化后的OPT函数伪代码：
bool getcard[5];
for(int i=0; i<5; i++){
        getcard[i] = false;
}//getcard[4]为了简化代码，没有实际的意义
getcard[0] = true;

int OPT(map<int,int>& m, int i){
        if(i>=m.size){
                   //分完四组牌
                   v1 = {x|map[x]==1};//所以分给第一个人的带序扑克牌
                   v2 = {x|map[x]==2};
                   v3 = {x|map[x]==3};
                   v4 = {x|map[x]==4};
                   return get21(v1)+get21(v2)+get21(v3)+get21(v4);
   }else{
                   int num[4];
                   for(int t=0; t<4; t++){
                           if(getcard[i]){[/i][/i][/i][i][i][i]                                   getcard[t+1] = true;
                                   map[i] = t+1;
                                   num[t][i] = OPT(m,i+1);[/i][/i][/i][/i][/i]  //回头看时发现这里有问题，改不了代码，绝望，修改放楼下了[i][i][i][i][i]
                           }else{[/i][/i][/i][/i][/i][i][i][i][i] num[t][i]  = 0; [/i][/i][/i][/i][/i][i][i][i][i][i]}[/i][/i][/i][/i][/i][i][i][i][i][i]                   }
                   return max(num[0],num[1],num[2],num[3]);
   }
}[/i][/i][/i][/i][/i]

qich 发表于 2017-5-22 13:39
看了一下楼主的求解过程，感觉楼主是看到了最开始的那个解法，那种解法是错误的，第二步用的是贪心，会陷 ...

bool getcard[5];
for(int i=0; i<5; i++){
        getcard = false;
}//getcard[4]为了简化代码，没有实际的意义
getcard[0] = true;

int OPT(map<int,int>& m, int i){
                if(i>=m.size){
                   //分完四组牌
                   v1 = {x|m[x]==1};//所以分给第一个人的带序扑克牌
                   v2 = {x|m[x]==2};
                   v3 = {x|m[x]==3};
                   v4 = {x|m[x]==4};
                   return get21(v1)+get21(v2)+get21(v3)+get21(v4);
   }else{
                int num[4];
                for(int t=0; t<4; t++){
                   if(getcard[t]){
                                if(getcard[t+1]){
                                        m[i] = t+1;
                                        num[t] = OPT(m,i+1);  
                                }else{
                                        getcard[t+1] = true;
                                        m[i] = t+1;
                                        num[t] = OPT(m,i+1);  //回头看时发现这里有问题，改不了代码，绝望，放楼下了
                                        getcard[t+1] = false;
                                }
                   }else{
                                num[t]  = 0;
                   }                  
                }
                return max(num[0],num[1],num[2],num[3]);
   }
}

求高手，做一下这个题啊。一点思路都没有。

DP
紫薯紫薯紫薯

是要求正好到21点吗？如果一个人手上有20点然后给他发个2，算不算成功一次？

必须恰好21点，任何时候手上的牌点之和必须小于等于21

挺有意思的题目，我正在思考解法。

請問ㄧ個人拿到 21 點，並把牌丟掉後，可以再從發牌人那拿牌嗎？

当然可以继续拿

有个不甚成熟的做法：
（1）如果把这个问题简化一下，就是只发给一个人，那么发牌人就只有两种选择，也就是{发牌，弃牌}。然后考虑这种情况下找到最优解，那么到一次集齐21点的情况（一个轮次），也就是满21的最后一张牌，牌的序号越前越好。这样我们可以找到一个轮次下的最优解，这样n个轮次之后，就会发完所有的牌，得到这个简化问题的最优解。
（2）那么考虑增加人数的情况，变成发牌给两人。这种情况下，可以从上面简化问题最优解得到的【弃牌堆】中继续得到21点的情况，弃牌堆也就是原来的发牌序列，去除已经发给第一人的牌，这样会组成一个新的牌堆，然后将这个牌堆发给第二个人，这又重复了第一个问题，同样的方法解得最优解。这种情况下，两次的最优解合并起来就得到了最终的最优解。
（3）如果有更多的人数，也就是不断重复步骤2而已。

没有经过严格证明，楼主可以看看这个解法有没有bug。

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

不行，我真是语死早，希望楼主能看懂我在说什么。