Balanced Partition

You are given an array, divide it into 2 equal halves such that the sum of those 2 halves are equal. (Imagine that such division is possible for the input array and array size is even)

--------------------------------------------------------------------

I‘ve met similar problem before :

Partition a set of numbers into two such that difference between their sum is minimum, and both sets have equal number of elements. 

In the past blog, DP[i][j] is defined whether a subset with size i could sum to j. However, a subset with size i is lengthy compared to the first i sub sequence. So the code could be written as :

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
int BalancedPartition(vector<int> v)
{
  int n = v.size();
  int sum = 0;
  for (int i = 0; i < v.size(); ++i)
    sum += v[i];

  int max_sum=sum/2,diff=INT_MAX;
  //int *s = new int[sum+1];
  //vector<int> s(sum + 1, 0);
  vector<vector<int>> s(n + 1, vector<int>(sum + 1,0));
  s[0][0] = 1;
  //for(int i=1; i<=sum; i++) s[i] = 0;
  for(int i=1; i<=n; i++)
  {
    for(int j = sum/2; j>=0; j--)
    {
      if(s[i-1][j])
      {
        s[i][j + v[i - 1]]=s[i - 1][j] + 1;
        s[i][j] = s[i - 1][j];
      }
    }
  }
  for(int j = sum/2; j>=1; j--)
    if(s[n][j])
    {
      return abs(sum-2*j);
    }
}
int main()
{
  int value[] = {12,5,7,3};
  int n = sizeof(value)/sizeof(value[0]);
  vector<int> v(value,value+n);
  cout<<BalancedPartition(v);
  return 0;
}

Similar to Knapsack problem, 2-d array could be changed into 1-d like this:

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
int BalancedPartition(vector<int> v)
{
  int n = v.size();
  int sum = 0;
  for (int i = 0; i < v.size(); ++i)
    sum += v[i];

  int max_sum=sum/2,diff=INT_MAX;
  //int *s = new int[sum+1];
  vector<int> s(sum + 1, 0);
  //vector<vector<int>> s(n + 1, vector<int>(sum + 1,0));
  s[0] = 1;
  //for(int i=1; i<=sum; i++) s[i] = 0;
  for(int i=1; i<=n; i++)
  {
    for(int j = sum/2; j>=0; j--)
    {
      //s[i][j] += s[i - 1][j];
      if (j >= v[i - 1] && s[j - v[i - 1]])
        s[j] += 1;
    }
  }
  for(int j = sum/2; j>=1; j--)
    if(s[j])
    {
      return abs(sum-2*j);
    }
}
int main()
{
  int value[] = {1,1,1,2,2,2,1,2};
  int n = sizeof(value)/sizeof(value[0]);
  vector<int> v(value,value+n);
  cout<<BalancedPartition(v);
  return 0;
}

Recursive Solution
Following is the recursive property of the second step mentioned above.

Let isSubsetSum(arr, n, sum/2) be the function that returns true if 
there is a subset of arr[0..n-1] with sum equal to sum/2

The isSubsetSum problem can be divided into two subproblems
 a) isSubsetSum() without considering last element 
    (reducing n to n-1)
 b) isSubsetSum considering the last element 
    (reducing sum/2 by arr[n-1] and n to n-1)
If any of the above the above subproblems return true, then return true. 
isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) ||
                              isSubsetSum (arr, n-1, sum/2 - arr[n-1])

#include <stdio.h>
 
// A utility function that returns true if there is a subset of arr[]
// with sun equal to given sum
boolisSubsetSum (intarr[], intn, intsum)
{
   // Base Cases
   if(sum == 0)
     returntrue;
   if(n == 0 && sum != 0)
     returnfalse;
 
   // If last element is greater than sum, then ignore it
   if(arr[n-1] > sum)
     returnisSubsetSum (arr, n-1, sum);
 
   /* else, check if sum can be obtained by any of the following
      (a) including the last element
      (b) excluding the last element
   */
   returnisSubsetSum (arr, n-1, sum) || isSubsetSum (arr, n-1, sum-arr[n-1]);
}
 
// Returns true if arr[] can be partitioned in two subsets of
// equal sum, otherwise false
boolfindPartiion (intarr[], intn)
{
    // Calculate sum of the elements in array
    intsum = 0;
    for(inti = 0; i < n; i++)
       sum += arr[i];
 
    // If sum is odd, there cannot be two subsets with equal sum
    if(sum%2 != 0)
       returnfalse;
 
    // Find if there is subset with sum equal to half of total sum
    returnisSubsetSum (arr, n, sum/2);
}
 
// Driver program to test above function
intmain()
{
  intarr[] = {3, 1, 5, 9, 12};
  intn = sizeof(arr)/sizeof(arr[0]);
  if(findPartiion(arr, n) == true)
     printf("Can be divided into two subsets of equal sum");
  else
     printf("Can not be divided into two subsets of equal sum");
  getchar();
  return0;
}

Time Complexity: O(2^n) In worst case, this solution tries two possibilities (whether to include or exclude) for every element.

Balanced Partition,布布扣,bubuko.com

Balanced Partition

原文：http://blog.csdn.net/taoqick/article/details/20243765