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.

$\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, 2014 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$ Apr 25, 2014 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, 2014 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$ Apr 26, 2014 at 17:03

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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