本文共 5384 字，大约阅读时间需要 17 分钟。

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. 

Knapsack problem:

Every bag weights 1 with related value, sum to max/2

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 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int BalancedPartition(vector
        
          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
         
           s(sum + 1, 0); vector
          
           
            > s(n + 1, vector
            
             (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
             
               v(value,value+n); cout<
             
            
           
          
         
        
       
      
     
    
   

A better version for this:

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int BalancedPartition(const vector
        
         & 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
         
           s(sum + 1, 0); vector
          
           
            > s(n + 1, vector
            
             (sum + 1,0)); for(int i=0; i<=n; i++) s[i][0] = 1; for(int i=1; i<=n; i++) { for(int j = sum/2; j>=v[i-1]; j--) { if (s[i-1][j-v[i-1]]) s[i][j] = s[i-1][j-v[i-1]] + 1; else 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
             
               v(value,value+n); cout<
             
            
           
          
         
        
       
      
     
    
   

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

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int BalancedPartition(vector
        
          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
         
           s(sum + 1, 0); //vector
          
           
            > s(n + 1, vector
            
             (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
             
               v(value,value+n); cout<
             
            
           
          
         
        
       
      
     
    
   

Recursive Solution

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/2The 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 
       
         // A utility function that returns true if there is a subset of arr[]// with sun equal to given sumboolisSubsetSum (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 falseboolfindPartiion (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 functionintmain(){  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.

转载地址：http://pwboi.baihongyu.com/