Finding maximum valued subset in which PartitionProblem algorithm returns true

Question

I´ve got the following assignment.

You have a multiset S with of 1<=N<=22 elements. Each element has a positive value of up to 10000000.

Assmuming that there are two subsets s1 and s2 of S in which the sum of the values of all the elements of one is equal to the sum of the value of all the elements of the other and it is the highest possible value. I have to return which elements of S would not be included in either of the two subsets.

Its probably been solved before, I think its some variant of the Partition problem but I can´t find it. If anyone could point me in the right direction that´d be great.

EDIT: An element can´t be in both subsets.

Are you familiar with the standard dynamic programming solutions to the 0/1 knapsack problem and partition problem? — templatetypedef, Aug 04 '15 at 22:02
I am and while I see how they´re similar problems I can't really figure out how to apply them here. Could you elaborate? — Federico Ruiz, Aug 04 '15 at 22:10

score 1 · Answer 1 · edited May 23 '17 at 12:00

This is variation of subset sum, and can be solved similarly, by increasing the dimension of the problem (and the DP matrix), and then applying a solution very similar to the original one for subset-sum, which follows the recursive formula:

D(i,x,y) = D(i-1,x,y)   OR    D(i-1,x-l[i],y)    OR    D(i-1,x,y-l[i])
             ^                       ^                       ^ 
           not chosen        chosen for first set         chosen for 2nd set

and base clause:

D(0,0,0) = true
D(0,x,y) = false        x!=0 or y!=0
D(i,x,y) = false        x<0 or y<0

After done calculating the DP matrix (3d array actyally) for this problem, all you have to do is find if there is any entry D(n,x,x) == true, for some x<= SUM/2 (where SUM is the sum of the entire original set), to find if there is any feasible solution.
Since you want the maximal value, the answer should be the maximal value of such x that D(n,x,x)=true (since there could be more than one)

Finding the elements themselves can be done after finding the solution (the value of x in D(n,x,x)) by following back the DP matrix and retracing your steps as explained for similar problems such as this: How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?

Total complexity of this solution is O(SUM^2 * n)

The sum can be rather large here. You could collapse `x, y` to `|x - y|`, but that still looks infeasible given the likely constraints. — David Eisenstat, Aug 05 '15 at 00:25

score 1 · Answer 2 · answered Aug 05 '15 at 00:50

Partition S as evenly as possible into T ∪ U (put the extra element, if any, in U). Loop through the three-way partitions of T into A ∪ B ∪ C (≤ 3¹¹ = 177,147 of them). Store the item |sum(A) - sum(B)| → C into a map, keeping only the value with the lowest sum in case the key already exists.

Loop through the three-way partitions of U into D ∪ E ∪ F. Look up |sum(D) - sum(E)| in the map; if it exists with value C, then consider C ∪ F as a possibility for the elements left out (the two parts with equal sum are either A ∪ D and B ∪ E, or A ∪ E and B ∪ D).

Finding maximum valued subset in which PartitionProblem algorithm returns true

2 Answers2

Linked

Related