I have n bags of candies such that no two bags have the same number of candies inside (i.e. it's a set A[] = {a0,a1,a2,...,ai,...,aj} where ai != aj ). I know how many candies is in each bag and the total number M of candies I have. I need to divide the bags among three children so that the candies are distributed as fairly as possible (i.e. each child gets as close to M/3 as possible). Needless to say, I may not tear into the bags to even out the counts -- then the question would be trivial. Does anyone have any thoughts how to solve this -- preferably in Java? EDIT: the interviewer wanted me to use a 2-D array to solve the problem: the first kid gets x, the second kid y, the third gets the rest: S[x][y] . This after I tried following: 1] sort array n lg n 2] starting with largest remaining bag, give bag to kid with fewest candy. Here is my solution for partitioning to two children (it is the correct answer). Maybe it will help with getting the 3-way partition. 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. }//

divide bags of candies among three children evenly

Reputation: 53586

Here is a little solution, crude but gives correct results. And you can even change the number of children, bags, 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;
   }

}

I don't know if this the result you were looking for, but it seems to be, from my understanding of the question.

Upvotes: 1

divide bags of candies among three children evenly

Answers (2)

Related Questions