### Code for Balanced Partitioning Dynamic Programming Problem

Can someone please explain this code in detail? I've tried debugging it but i can't figure out how it produces the result. I've been searching for a solution for the problem and this is the code that I stumbled upon, it produces accurate solutions and I would like to know how it works. Many thanks.

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455`` ``````#include #include #include #include #include using namespace std; int BalancedPartition ( int a[] , int n ) { int sum = 0; for( int i = 0 ; i < n ; i++) sum += a[i]; int *s = new int[sum+1]; s[0] = 1; for(int i = 1 ; i < sum+1 ; i++) s[i] = 0; int diff = INT_MAX , ans; for(int i = 0 ; i < n ; i++) { for(int j = sum ; j >= a[i] ; j--) { s[j] = s[j] | s[j-a[i]]; if( s[j] == 1 ) { if( diff > abs( sum/2 - j) ) { diff = abs( sum/2 - j ); ans = j; } } } } return sum-ans-ans; } int main() { int n,result, arr[300]; cin >>n; for(int i = 0; i < n; i++) { cin>>arr[i]; } result = BalancedPartition(arr,n); cout <
Can you explain what you were looking for that this code does so well? Like what are the inputs used for and what does the result mean?

E: http://www.cs.cornell.edu/~wdtseng/icpc/notes/dp3.pdf
Last edited on
I want to know how the function finds the two subsets, it works great because I've tested it for up to 300 inputs which sum adds up to 100,000.

Example: a set of numbers {1,5,9,3,8}, now the solution is two subsets, one subset with elements {9,3} and the other {8,5,1} the sum of the first one is 13 and the sum of the second is 13 so the difference between the sums is 0. The result shows the difference between the sums.

Another example: a set of numbers where the difference between the subsets cannot be zero, {9 51 308 107 27 91 62 176 28 6}, the minimal difference between the two subsets is 2.
Last edited on
I was going to mention this in the first post, but I tried 5,4,3,7,9 and it returned 0.

This should work because {4,3,7} = 14 and {9,5} = 14

OT/

 I want to know how the function finds the two subsets,

The link I posted describes the algorithm. I can't say I understand why they did it the way it was done, but it seems to work great. Maybe someone on the forum who is good at this can explain what it does
Topic archived. No new replies allowed.