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

Question

我有 n 袋糖果，因此没有两个袋子里面的糖果数量相同(即它是一组 A[] = {a0,a1,a2,... ,ai,...,aj 其中ai != aj).

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

我需要将袋子分给三个 child ，以便尽可能公平地分配糖果(即每个 child 尽可能接近 M/3)。

不用说，我可能不会撕破袋子来平衡计数——这样问题就微不足道了。

有没有人想过如何解决这个问题——最好是用 Java？

编辑:

面试官要我用一个二维数组来解决这个问题:第一个 child 得到 x，第二个 child 得到 y，第三个得到剩下的:S[x][y] .

这是在我尝试以下之后:

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

---

这里是我对两个 child 进行分区的解决方案(这是正确答案)。也许这有助于获得 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.
}//

Answer 1

您描述的问题称为 3-Partition problem并且已知是 NP 难的。在 MathOverflow 上讨论了这个问题。 .您可能会在那里找到一些有值(value)的指示。