I know this was talked over a lot here, but I am struggling with this problem.
We have a set of numbers, e.g [3, 1, 1, 2, 2, 1], and we need to break it into two subsets, so the each sum is equal or difference is minimal.
I've seen wikipedia entry, this page (problem 7) and a blog entry.
But every algorithm listed is giving only YES/NO result and I really don't understand how to use them to print out two subsets (e.g S1 = {5, 4} and S2 = {5, 3, 3}). What am I missing here?
Balanced number partitioning is a variant of multiway number partitioning in which there are constraints on the number of items allocated to each set. The input to the problem is a set of n items of different sizes, and two integers m, k.
In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset.
Graph partitioning can be done by recursively bisecting a graph or directly partitioning it into k sets. There are two ways to partition a graph, by taking out edges, and by taking out vertices. Graph partitioning algorithms use either edge or vertex separators in their execution, depending on the particular algorithm.
There is an optimization version of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized. The optimization version is NP-hard, but can be solved efficiently in practice.
The pseudo-polynomial algorithm is designed to provide an answer to the decision problem, not the optimization problem. However, note that the last row in the table of booleans in the example indicates that the current set is capable of summing up to N/2.
In the last row, take the first column where the boolean value is true
. You can then check what the actual value of the set in the given column is. If the sets summed value is N/2 you have found the first set of the partition. Otherwise you have to check which set is capable of being the difference to N/2. You can use the same approach as above, this time for the difference d.
This will be O(2^N). No Dynamic Programming used here. You can print result1, result2 and difference after execution of the function. I hope this helps.
vector<int> p1,p2;
vector<int> result1,result2;
vector<int> array={12,323,432,4,55,223,45,67,332,78,334,23,5,98,34,67,4,3,86,99,78,1};
void partition(unsigned int i,long &diffsofar, long sum1,long sum2)
{
if(i==array.size())
{
long diff= abs(sum1 - sum2);
if(diffsofar > diff)
{
result1 = p1;
result2 = p2;
diffsofar = diff;
}
return;
}
p1.push_back(array[i]);
partition(i+1,diffsofar,sum1+array[i],sum2);
p1.pop_back();
p2.push_back(array[i]);
partition(i+1,diffsofar,sum1,sum2+array[i]);
p2.pop_back();
return;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With