2

我有n一袋糖果，所以没有两个袋子里面有相同数量的糖果（即它是一组A[] = {a0,a1,a2,...,ai,...,aj}where 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.
}//
4

2 回答 2

3

您描述的问题被称为3-Partition 问题，并且被称为 NP-hard。这个问题在MathOverflow上进行了一些讨论。您可能会在那里找到一些有价值的指针。

于 2012-04-20T22:03:26.417 回答
1

这是一个小解决方案，粗略但给出了正确的结果。你甚至可以改变孩子、包包等的数量。

public class BagOfCandies {

   static public void main(String...args) {
      int repeat = 10;
      int childCount = 3;
      int bagsCount = childCount + (int) (Math.random() * 10);

      for (int k=0; k<repeat; k++) {
         int candyCount = 0, n=0;
         int[] bags = new int[bagsCount];
         for (int i=0; i<bags.length; i++) {
            n += 1 + (int) (Math.random() * 2);
            bags[i] = n;
            candyCount += n;
         }
         shuffle(bags);   // completely optional! It works regardless

         boolean[][] dist = divideBags(bags, childCount);

         System.out.println("Bags of candy : " + Arrays.toString(bags) + " = " + bags.length);
         System.out.println("Total calculated candies is " + candyCount);
         int childCandySum = 0;
         for (int c=0; c<childCount; c++) {
            int childCandies = countSumBags(bags, dist[c]);
            System.out.println("Child " + (c+1) + " = " + childCandies + " --> " + Arrays.toString(dist[c]));
            childCandySum += childCandies;
         }
         System.out.println("For a total of " + childCandySum + " candies");
         System.out.println("----------------");
      }
   }

   static private void shuffle(int[] bags) {
      for (int i=0, len=bags.length; i<len; i++) {
         int a = (int)Math.floor(Math.random()*len);
         int b = (int)Math.floor(Math.random()*len);
         int v = bags[a];
         bags[a] = bags[b];
         bags[b] = v;
      }
   }

   static private boolean[][] divideBags(int[] bags, int childCount) {
      int bagCount = bags.length;

      boolean[][] dist = new boolean[childCount][bagCount];
      for (int c=0; c<childCount; c++) 
         Arrays.fill(dist[c], false);

      for (int i=0; i<bagCount; i+=childCount)
         for (int j=i, c=0; c<childCount && j<bagCount; j++, c++)
            dist[c][j] = true;

      if (childCount == 1) return dist;  // shortcut here

      int sumDiff = 1;
      int oldDiff = 0;

      while (sumDiff != oldDiff) {
         oldDiff = sumDiff;
         sumDiff = 0;

         // start comparing children in pair
         for (int child1=0; child1<childCount-1; child1++) {
            for (int child2=child1+1; child2<childCount; child2++) {

               int count1 = countSumBags(bags, dist[child1]);
               int count2 = countSumBags(bags, dist[child2]);
               int diff = Math.abs(count1 - count2);

               // a difference less than 2 is negligeable
               if (diff > 1) {
                  // find some bags with can swap to even their difference
                  int c1=-1, c2=-1, cdiff;
                  boolean swap = false;

                  for (int i=0; i<bagCount-1; i++) {
                     for (int j=i; j<bagCount; j++) {
                        if (dist[child1][i] && dist[child2][j]) {
                           cdiff = Math.abs((count1 - bags[i] + bags[j]) - (count2 + bags[i] - bags[j]));
                           if (cdiff < diff) {
                              c1 = i; c2 = j;
                              diff = cdiff;
                              swap = true;
                           }
                        }
                        if (dist[child1][j] && dist[child2][i]) {
                           cdiff = Math.abs((count1 - bags[j] + bags[i]) - (count2 + bags[j] - bags[i]));
                           if (cdiff < diff) {
                              c1 = j; c2 = i;
                              diff = cdiff;
                              swap = true;
                           }
                        }
                     }
                  }

                  if (swap) {
                     //System.out.println("Swaping " + c1 + " with " + c2);
                     dist[child1][c1] = false; dist[child1][c2] = true;
                     dist[child2][c1] = true;  dist[child2][c2] = false;
                  }
               }

               //System.out.println("Diff between " + child1 + "(" + countSumBags(bags, dist[child1]) + ") and " + child2 + "(" + countSumBags(bags, dist[child2]) + ") is " + diff);

               sumDiff += diff;
            }
         }

         //System.out.println("oldDiff="+oldDiff+", sumDiff="+sumDiff);
      }

      return dist;
   }

   static private int countSumBags(int[] bags, boolean[] t) {
      int count = 0;
      for (int i=0; i<t.length; i++) {
         if (t[i]) {
            count+=bags[i];
         }
      }
      return count;
   }

}

我不知道这是否是您正在寻找的结果，但根据我对问题的理解，它似乎是。

于 2012-04-20T21:18:35.997 回答