diviser les sacs de bonbons entre trois enfants de manière égale

Question

J'ai n sacs de bonbons tels que deux sacs n'ont pas le même nombre de bonbons à l'intérieur (c'est-à-dire que c'est un ensemble A[] = {a0,a1,a2,...,ai,...,aj} donde ai != aj ).

Je sais combien de bonbons il y a dans chaque sac et le nombre total M de bonbons que j'ai.

Je dois répartir les sacs entre trois enfants de façon à ce que les bonbons soient distribués le plus équitablement possible (c'est-à-dire que chaque enfant reçoive le plus près possible de la quantité de bonbons qu'il désire). M/3 dans la mesure du possible).

Inutile de dire que je ne vais peut-être pas déchirer les sacs pour égaliser les comptes - la question serait alors triviale.

Quelqu'un a-t-il une idée de la façon de résoudre ce problème, de préférence en Java ?

EDITAR:

l'interviewer voulait que j'utilise un tableau à deux dimensions pour résoudre le problème : le premier enfant reçoit x, le deuxième y, le troisième le reste : S[x][y] .

Ceci après que j'ai essayé de suivre :

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

---

Voici ma solution pour le partitionnement en deux enfants (c'est la bonne réponse). Peut-être que cela vous aidera à obtenir la partition à trois.

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

Le problème que vous décrivez est connu sous le nom de 3-Problème de partition et est connu pour être NP-hard. Le problème est discuté un peu sur MathOverflow . Vous trouverez peut-être certains des conseils qui y sont donnés utiles.

Answer 2

Voici une petite solution, grossière mais qui donne des résultats corrects. Et vous pouvez même modifier le nombre d'enfants, de sacs, etc.

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

}

Je ne sais pas si c'est le résultat que vous recherchiez, mais il semble l'être, d'après ma compréhension de la question.