Dynamic programming to find two subsets

Question

Let X,Y subsets of {1,...,100n} where |X|=3n and |Y|=7n. Find A subset of X and B subset of Y such that: both are not empty, |A|=|B| and sum a_i = sum b_i.

There are O(n^2) sums we can make of the set \{1,...,100n\} (the largest one is 1+... +100n even though this one isn't possible since X and Y don't include all numbers)
There are O(n) cardinals (set sizes) for every sum (from the previous bullet)
We can have a table of \{0,1\} (booleans) with the size of O(n) X O(n^2) where rows represents cardinality and columns represents a number. So 1 means we can create a subset with cardinality i and the sum of the set is j
First row/column is easy to calculate of course

Now basically I need to iterate all cells and update them in O(n) per cell. So we shall end-up with an overall time-complexity of O(n^4).

How can I do that?

I think I could iterate it row by row; Meaning, if I want to update the cell T[i,j] (Meaning, a set with a size i of sum j), then I could look for a set of size i-1 plus some term which equals together j.

BUT! It could be that we already used this term in the previous set (of size i-1) - Problem!

A. Sarid · Accepted Answer · 2016-09-27 11:37:14Z

1

You were almost there. Your dynamic programming should contain another parameter:

Lets define DP[K,J,I] to be the number of subsets with size K of the first I elements that sums to J. The idea of this dynamic programming is that for each element i in the set, we check both cases - with adding it to our subset and without adding it.

DP[0,0,i] = 1
DP[k,j,0] = 0
DP[k,j,i] = DP[k-1,j-S[i],i-1] or DP[k,j,i-1]

edited Sep 27, 2016 at 11:37

answered Sep 17, 2016 at 20:26

A. Sarid

4,0042 gold badges34 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Dynamic programming to find two subsets

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related