0
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\begingroup$ This question does not necessarily ask for a solution. $\endgroup$
    – Fredrik
    May 3, 2016 at 18:15
  • $\begingroup$ Is T fixed? ​ ​ $\endgroup$
    – user12859
    May 3, 2016 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, 2016 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, 2016 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, 2016 at 19:08

0

Reset to default

Browse other questions tagged or ask your own question.