[Solved]: Is it possible to easily reduce 0/1 subset sum to subset sum with multiplicities?

Problem Detail: 

So both the 0/1 subset sum problem (find a subset of given numbers that add up to a target sum) and the subset sum problem with "multiplicities" (find non-negative integer coefficients for the set elements so that the linear combination of set elements equals a target sum) are NP-complete. Is there some fairly easy reduction from 0/1 subset-sum to subset sum with multiplicities? This seems perhaps non-trivial, because just because there is a solution with multiplicities doesn't mean there is a 0/1 solution.

Some ideas I had that don't seem to work: For element $s$, solve the subset sum with multiplicity problem both for total sum $S$ and $S-s$ with element $s$ removed from the set. Then try to argue that $s$ either is or is not included in the 0/1 solution depending on the answer.

Asked By : user2566092

Answered By : D.W.

This answer on CSTheory describes a reduction from 0/1 subset-sum to the unbounded knapsack problem (UKP). That does exactly what you want. The intuition is that UKP is basically subset sum with multiplicities, since UKP lets you put as many copies of an item as you want into your knapsack.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24117

3.2K people like this

 Download Related Notes/Documents