# Is it possible to easily reduce 0/1 subset sum to subset sum with multiplicities?

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.

• Would you like to share with us what approaches you have tried? Try looking at other problems that have nice reductions to/from subset-sum (e.g., the knapsack problem, the partition problem). Your question looks essentially the same as asking whether there is an easy reduction from the unbounded knapsack problem (UKP) to 0/1 subset-sum. I think that's answered here: cstheory.stackexchange.com/q/1000/5038 – D.W. Apr 25 '14 at 21:01
• @D.W. I'm asking for the reduction to go the other way, but your link is interesting. I'll update with what I've tried. – user2566092 Apr 25 '14 at 21:22
• Actually, I think the reduction in that cstheory answer is exactly what you are looking for. I think that reduction goes the right way, I just described it backwards in my comment (my mistake). That reduction is actually a reduction from 0/1 subset-sum to UKP, so I think it's exactly what you wanted. Maybe take another look at Kristoffer Arnsfelt Hanser's answer? (I hope I'm not making a stupid mistake!) – D.W. Apr 26 '14 at 5:33
• @D.W. Actually you're right, I read the reduction in that answer and it is what I'm looking for. If you post as an answer, I'll upvote and accept. – user2566092 Apr 26 '14 at 17:03