3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ – D.W.♦ Apr 25 '14 at 21:01
  • $\begingroup$ @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. $\endgroup$ – user2566092 Apr 25 '14 at 21:22
  • $\begingroup$ 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!) $\endgroup$ – D.W.♦ Apr 26 '14 at 5:33
  • $\begingroup$ @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. $\endgroup$ – user2566092 Apr 26 '14 at 17:03
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.