Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

#1
July 5th, 2012, 12:44 PM
 touches
Registered User

Join Date: Jul 2009
Posts: 8
Time spent in forums: 2 h 36 m 16 sec
Reputation Power: 0
Understanding Balanced Partition Algorithm-Help

Hi all, before i write C code for the Balanced Partition Problem, i am trying to understand the algorithm behind it, i seem to know a few ifs and buts of the algorithm but i have not properly understood the logic behind the maths. I googled the algorithm and almost every forum has a link to MIT's video on it, anyways here's the link

http://people.csail.mit.edu/bdean/6.046/dp/ . I am able to understand the requirements of the problem (i.e)
Given N integers eg:5 8 13 27 14 the minimum sum is 3 as (13+8+14)-(5+27)=3.
But i am unable to understand the algorithmic logic.
for eg: in the above video how does P(i,j) be equal to 1 is there exists a subset of values(a1...ai) which has a sum of j.
I'd like to understand the derivation behind it. Any explanation with numeric examples would be of great aid.

 Viewing: Dev Shed Forums > Other > Beginner Programming > Understanding Balanced Partition Algorithm-Help