2

私はn2 つの袋の中に同じ数のキャンディーが入っていないように、キャンディーの袋を持っています (つまり、 のセットA[] = {a0,a1,a2,...,ai,...,aj}ですai != aj)。

各袋にいくつのキャンディーが入っているか、また持っているキャンディーの総数を知っMています。

キャンディーができるだけ公平に分配されるように (つまり、各子供がM/3できるだけ近くにくるように)、バッグを 3 人の子供に分ける必要があります。

言うまでもなく、数を均等にするために袋を引き裂くことはできません。そうであれば、問題は些細なことです。

これを解決する方法を考えている人はいますか - できれば Java で？

編集：

インタビュアーは、問題を解決するために 2 次元配列を使用するように私に求めましたS[x][y]。

これは、次のことを試した後です：

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

これが、2 つの子に分割するための私の解決策です (正解です)。たぶん、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 困難であることが知られています。この問題は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 に答える