Sunday, August 3, 2014

Partition an array of integers into sub-arrays so that the difference of summaries (of sub-arrays) is minimal


Here is one solution (dynamic programming) for partition an array of integers into two sub-arrays so that the difference of summaries (of sub-arrays) is minimal.
// partition an array of integers into two sub-arrays so that the difference of summaries (of sub-arrays) is minimal
int balancePartitionTwoWays(int arr[], int n, int partition[2]) {

 if (n==2) {
  for (int i=0; i<2; i++) {
   partition[i]=arr[i];
  }
  return abs(partition[0]-partition[1]);
 }


 // loop through the array to find out the sum and maximum
 int sum=0;
 int maximum = -1;
 for(int i=0; i<n; i++){
  sum += arr[i];
  if (arr[i]>maximum) maximum = arr[i];
 }

 // allocate the matrix to remember
 bool memo[sum+maximum+1][2];
 for (int j = 0; j < 2; j++)
  for (int i = 0; i <= sum+maximum; i++)
    memo[i][j] = false;

 memo[0][0] = true;

 // mark memo[i][k] to true if there is a subset
    // of array [0..i-1] with sum equal to i
 for (int j = 0; j < n; j++) {
  for (int i = 0; i <= sum+maximum; i++) {

   if (memo[i][j%2]) {
    memo[i][(j+1)%2] = true;
    memo[i+ arr[j]][(j+1)%2] = true;

   }
  }
 }

 int max_diff = INT_MAX;
 int part[2];

 for (int i = 0; i <= sum+maximum; i++) {
  if (memo[i][n % 2]) {
   part[0]=i;
   part[1]=sum-i;
   int temp = abs(part[0]-part[1]) ;
   if (temp<max_diff) {
    max_diff = temp;
    partition[0] = part[0];
    partition[1] = part[1];
   }
  }
 }

 return max_diff;

}



// partition an array of integers into three sub-arrays so that the difference of summaries (of sub-arrays) is minimal
int balancePartitionThreeWays(int arr[], int n, int partition[3]) {

 if (n==3) {
  for (int i=0; i<3; i++) {
   partition[i]=arr[i];
  }
  return abs(partition[0]-partition[1]) + abs(partition[1]-partition[2]) + + abs(partition[2]-partition[0]);
 }


 // loop through the array to find out the sum and maximum
 int sum=0;
 int maximum = -1;
 for(int i =0; i<n; i++){
  sum += arr[i];
  if (arr[i]>maximum) maximum = arr[i];
 }

 // allocate the matrix to remember
 bool memo[sum+maximum+1][sum+maximum+1][2];
 for (int k = 0; k < 2; k++)
  for (int i = 0; i <= sum+maximum; i++)
   for (int j = 0; j <= sum+maximum; j++)
    memo[i][j][k] = false;

 memo[0][0][0] = true;

 // mark memo[i][j][k] to true if there is a subset
    // of array [0..i-1] with sum equal to i
 for (int k = 0; k < n; k++) {
  for (int i = 0; i <= sum+maximum; i++) {
   for (int j = 0; j <= sum+maximum; j++) {
    if (memo[i][j][k%2]) {
     memo[i][j][(k+1)%2] = true;
     memo[i+ arr[k]][j][(k+1)%2] = true;
     memo[i][j+ arr[k]][(k+1)%2] = true;
    }
   }
  }
 }

 int max_diff = INT_MAX;
 int part[3];

 for (int i = 0; i <= sum+maximum; i++) {
  for (int j = 0; j <= sum+maximum; j++) {

   if (memo[i][j][n % 2]) {
    part[0]=i;
    part[1]=j;
    part[2]=sum-i-j;

    //int temp = abs(part[0]-part[1]) + abs(part[1]-part[2]) + + abs(part[2]-part[0]);
    int temp = 0;
    for (int k=0; k<3; k++) {
     temp += abs(part[k%3]-part[(k+1)%3]);
    }
    if (temp<max_diff) {
     max_diff = temp;
     for (int k=0; k<3; k++) {
      partition[k]=part[k];
     }
    }
   }
  }
 }

 return max_diff;

}



Enjoy the journey. 

8 comments:

  1. I must thank you for the efforts you have put in penning this site. I am hoping to check out the same high-grade content by you later on as well. In truth, your creative writing abilities has inspired me to get my own, personal blog now..

    Linux Training in Chennai

    ReplyDelete
  2. This blog is having the general information. Got a creative work and this is very different one.We have to develop our creativity mind.This blog helps for this. Thank you for this blog. This is very interesting and useful.

    ccna training in chennai thiruvanmiyur

    ReplyDelete
  3. This is an awesome post.Really very informative and creative contents. These concept is a good way to enhance the knowledge.I like it and help me to development very well.Thank you for this brief explanation and very nice information.Well, got a good knowledge.

    PPC Services in Chennai

    ReplyDelete
  4. I think it's awesome someone is finally taking notice of our vet's and doing something to help them. I hope all goes well with these articles. More new information i will get after refer that post.
    Restaurant Interior Designers in Chennai
    Turnkey Interiors in Chennai
    Corporate Office Interiors in Chennai

    ReplyDelete
  5. It’s really amazing that we can record what our visitors do on our site. Thanks for sharing this awesome guide. I’m happy that I came across with your site this article is on point,thanks again and have a great day. Keep update more information..
    Fleet Management Software
    Manufacturing ERP
    Logistic ERP
    Logistics Software
    Human resources management software

    ReplyDelete
  6. Fertility is the natural capability to produce offspring. As a measure, fertility rate is the number of offspring born per mating pair, individual or population.Human fertility depends on factors of nutrition, sexual behavior, consanguinity, culture, instinct, endocrinology, timing, economics, way of life, and emotions.Greate thinks of a fertility center for humans.

    Fertility Center in OMR

    ReplyDelete