0

I need to find the optimal subsets after solving the partition problem using the Dynamic Programming pseudo polynomial time algorithm.

More specifically, I'm not able to make sense of this answer: https://stackoverflow.com/a/890243/1317826

I'm not able to understand how to construct the optimal subsets from the boolean table.

The Wikipedia article on the partition problem has it too: http://en.wikipedia.org/wiki/Partition_problem

Can someone please shed some light on it?

Community
  • 1
  • 1
Bruce
  • 945
  • 3
  • 12
  • 24
  • I think it is better if you describe what you understood in you own words to see how the community can help you – Regenschein Jun 19 '13 at 11:15

1 Answers1

1

Everything you need is in the answer you posted.

First of all, when you create table using pseudo-polynomial time algorithm you don't store boolean values (True if it's reachable, False otherwise), but value of the element that you added to the subset. Than you should be able to construct subset by simply substracting it from the sum you obtained.

So the algorithm is:

  1. For every number x_i in your set:

    1. Set p(1, x_i) = x_i

    2. For every other field p(row, sum) set it to x_i if p(row-1, sum-x_i) != 0

  2. So now p(row, sum) = x means that we can get sum by taking some row elements of our set and last one of them is x.

  3. Once p(some_row, N/2) != 0 you can construct the subset by taking it's value x, and moving to p(some_row - 1, N/2 - x) and so forth.

Hope this makes it clear.

BTW. Is there a way to write latex in the answers?

warran
  • 184
  • 1
  • 10