0
$\begingroup$

This question already has an answer here:

The problem looks a bit like the knapsack problem, but here the objects placed in the sack are unique and it is allowed to overflow the sack. The main goal is to see if it is possible to fill all of the sacks.

PROBLEM: Say I have a set of unique buckets $Q = \{4,2,7,1\}$, where the value indicates the space of each bucket. Also, I have a set of unique objects $T = \{1,3,2,2,4,3\}$ where the value of each indicates the spaces it takes up.

Overflowing values are discarded, meaning that you can't split an object between buckets.

Is there a way for me to take those unique objects and place them in the buckets such that all of the buckets are filled - overflow is allowed.


My question: For a given number of buckets $Q$ and objects $T$ - I wish to show this is NP-Complete by reducing from the Subset Sum problem. How would I go about doing this?

$\endgroup$

marked as duplicate by D.W. May 3 '16 at 19:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ This question does not necessarily ask for a solution. $\endgroup$ – Fredrik May 3 '16 at 18:15
  • $\begingroup$ Is T fixed? ​ ​ $\endgroup$ – user12859 May 3 '16 at 18:45
  • 1
    $\begingroup$ Don't re-post your post after it's been closed. I already provided a comment indicating what you should do if you want the question to be re-opened. In particular, you should read the material in our reference question (which answers exactly the question you asked -- how do you go about construct a reduction? -- but in more general terms), work through your problem again, and then if you still can't solve your problem, edit this question to show us your attempts. $\endgroup$ – D.W. May 3 '16 at 19:00
  • $\begingroup$ (repeating the prior comment, for context) Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. What have you tried? Where did you get stuck? This is a nice exercise, but we do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. I suggest you work through our reference question, then if you still can't solve it, edit your question to show what you tried and where you got stuck. $\endgroup$ – D.W. May 3 '16 at 19:01
  • $\begingroup$ it looks like you might have accidentally created multiple accounts. If so, I encourage you to merge them: cs.stackexchange.com/help/merging-accounts. I also encourage you to create an account, to ensure you'll retain access to them: cs.stackexchange.com/help/why-register. $\endgroup$ – D.W. May 3 '16 at 19:08

Browse other questions tagged or ask your own question.