java - 将糖果袋平均分给三个 child

我有n袋糖果，所以没有两个袋子里面有相同数量的糖果（即，这是一组A[] = {a0,a1,a2,...,ai,...,aj}，其中ai != aj）。

我知道每个袋子里有多少糖果，以及我拥有的糖果总数M。

我需要将袋子分配给三个孩子，以便尽可能公平地分配糖果（即，每个孩子离M/3越近越好）。

毋庸置疑，我可能不会掏腰包来平分账单，那么这个问题将变得微不足道。

有没有人想到如何解决这个问题-最好是在Java中？

编辑：

面试官要我使用二维数组解决问题：第一个孩子得到x，第二个孩子y，第三个孩子得到其余的：S[x][y]。

我尝试以下操作后：

1] sort array n lg n
2] starting with largest remaining bag, give bag to kid with fewest candy.

这是我的划分为两个孩子的解决方案（这是正确的答案）。也许它将有助于获得3路分区。

int evenlyForTwo(int[] A, int M) {
    boolean[] S = new boolean[M+1];
    S[0]=true;//empty set
    for(int i=0; i<A.length; i++)
        for(int x=M; x >= A[i]; x--)
            if(!S[x])
                S[x]=S[x-A[i]];
    int k = (int) M/2;
    while(!S[k])
        k--;
    return k;//one kid gets k the other the rest.
}//

最佳答案

您描述的问题称为3-Partition problem，并且已知为NP难题。在MathOverflow上讨论了该问题。您可能会在其中找到一些有价值的指针。