Ronzii's Blog

Just your average geek's blog

Balanced Partition Problem

Follow the logic of Balanced Partition Problem from here

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
int BalancedPartition(vector<int> v)
{
    int n = v.size();
    int sum = accumulate(v.begin(),v.end(),0);
    int max_sum=sum/2,diff=INT_MAX;
    int *s = new int[sum+1];
    s[0] = 1;
    for(int i=1; i<=sum; i++) s[i] = 0;
    for(int i=0; i<n; i++)
    {
        for(int j = sum; j>=0; j--)
        {
            if(s[j])
            {
                s[j+v[i]]+=1;
            }
        }
    }
    for(int j = sum/2; j>=1; j--)
        if(s[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;
}
Advertisements

March 19, 2012 - Posted by | C++, Dynamic Programming | , , , , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s