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.

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..

ReplyDeleteLinux Training in Chennai

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.

ReplyDeleteccna training in chennai thiruvanmiyur

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.

ReplyDeletePPC Services in Chennai