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 | , , , , , , | Leave a comment

Red Black Tree’s Rotation

class RedBlackNode
{
public:
    int key;
    int color;
    RedBlackNode* left;
    RedBlackNode* parent;
    RedBlackNode* right;
    RedBlackNode()
    {
    }
    RedBlackNode(int n)
    {
        left = right = parent = NULL;
        key = n;
        color = RED;
    }
    ~RedBlackNode()
    {
    }
};
void LeftRotate(RedBlackNode* x)
{
	RedBlackNode* y = new RedBlackNode;
	y = x->right;
	x->right = y->left;
	if(y->left!=nil)
	{
		y->left->parent = x;
	}
	if(x->parent == nil)
	{
		root = x;
	}
	else if(x->parent->left ==x)
	{
		x->parent->left = y;
	}
	else
	{
		x->parent->right = y;
	}
	y->left = x;
	x->parent = y;
}
void RightRotate(RedBlackNode* y)
{
	RedBlackNode* x = new RedBlackNode;
	x = y->left;
	y->left = x->right;
	if(x->right!=nil)
	{
		x->right->parent = y;
	}
	if(y->parent==nil)
	{
		root = y;
	}
	else if(y->parent->left==y)
	{
		y->parent->left = x;
	}
	else
	{
		y->parent->right = x;
	}
	x->right = y;
	y->parent = x;
}

July 21, 2011 Posted by | C++ | , , , | Leave a comment