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

qich 发表于 2017-5-17 20:43
我语言表达能力实在捉急，简单的写了个代码：

int getN(vector& cards, int begin, int n){

哈哈哈谢谢层主~昨天没看到
层主关于一个人的思路应该是对的，我之前把层主的“牌的序号越前越好”的牌理解成找组合成21的最前面的牌了，实际上层主说的是最后一张。这样也要找很多但比遍历简单很多，而且我觉得是没bug的

发给多个人的情况我还没想清楚，先不乱讲了

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

谢谢你提供算法的解。假如牌的序列如下，你能算一下最后的解吗？
String cards="5,10,8,5,2,3,J,Q,9,A,K,9,9,5,6,K,10,8,Q,Q,6,4,K,2,J,Q,6,T,8,A,3,K,7,J,9,7,A,4,4,7,3,5,2,8,J,6,3,4,2,7,A,10"

我使用你的方法，对如下的牌进行了实验。耗的时间太久，没有算出结果来，可能是我理解的方法不对。我是：发给第一个人的牌，如果有多种解，全部一个一个试。发给第二个人的牌，如果有多种解，也一个一个的试。这样全局取优，可能性太多了。
比如发给第一个人的牌，下面是几个轮次找21点的返回下标的结果：
the last index of the 21 point:5
the last index of the 21 point:9
the last index of the 21 point:14
the last index of the 21 point:29
the last index of the 21 point:36
the last index of the 21 point:42
the last index of the 21 point:46
the last index of the 21 point:51


从下标0到5，产生21点有2种可能
从下标6到9，产生21点有3种可能
从下标10到14，产生21点有1种可能
从下标15到29，产生21点有79种可能
从下标30到36，产生21点有9种可能
从下标37到42，产生21点有2种可能
从下标43到46，产生21点有1种可能
从下标47到51，产生21点有2种可能

总共发牌给第一个人有：2 x 3 x 1 x 79 x 9 x 2 x 1 x 2=17064 种可能

下面来关注，从下标15，到29这一段牌：K,10,8,Q,Q,6,4,K,2,J,Q,6,T,8,A
从这一段牌中找21点，共有79种可能，这个数太大，导致接下来全局取优化的时候，需要实验的数目变得异常的大。

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]

我在上一楼只进行了最简单的优化，示意一下动规的优化空间，实际上这个算法还可以进一步进行时间复杂度的优化。

想了一个很简陋的递推方程，不知道对不对：
f[0,0,0,0,0]=1
for (card: cards)
f[i+1,j+card,k,l,m]=f[i+1,j+card,k,l,m]+f[i,j,k,l,m]
f[i+1,j,k+card,l,m]=f[i+1,j,k+card,l,m]+f[i,j,k,l,m]
...
f[i+1,j,k,l,m]=f[i+1,j,k,l,m]+f[i,j,k,l,m]
当然还要加上大于21点弃牌的项和保存中间项，最后遍历一次f[51,*,*,*,*]就可以获得答案了，O(52*21^4)

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]);
   }
}

~确保每一个每个player都拥有完整的 一套 group {1，2,  3,  4, ..., J, Q, K, A} 不知道行不。发现自己想多了~~~