1
$\begingroup$

I was wondering whether I can solve the following problem by using a greedy strategy: Let's say that I have a set of containers with 2 dimensions (width and height) and a set of items also with 2 dimensions. Can a solution be found where each item is assigned to a container so that it fits inside? I can have containers left over; however, all of the items must be assigned. Assuming a solution exist, is there a greedy choice I can make for assigning an item to a container?

$\endgroup$
  • $\begingroup$ Have you tried looking for such a strategy? $\endgroup$ – Yuval Filmus Dec 21 '16 at 9:33
  • $\begingroup$ I have and am still looking. I'm currently trying by selecting an item that is not fully contained by another item and assigning that to some container, however i'm completely blacking out trying (informally) proof this. I've tried some more strategies, however I can't seem to wrap my head around the problem. $\endgroup$ – Henk Dec 21 '16 at 9:38
  • 1
    $\begingroup$ Do the containers have the same capacity? Also, if your goal is to minimize the number of containers that are used, you should check Bin Packing $\endgroup$ – Sorrop Dec 21 '16 at 10:00
  • $\begingroup$ When you say "2 dimensions", do you mean two parameters (like volume and weight) or do you mean width and height? In other words, are you looking for numerical packing or geometric packing? $\endgroup$ – Karolis Juodelė Dec 21 '16 at 10:09
  • 1
    $\begingroup$ For the future, one way you can approach this is to try using the methods found here: cs.stackexchange.com/q/59964/755. $\endgroup$ – D.W. Dec 21 '16 at 22:59
2
$\begingroup$

No, a greedy approach would not guarantee a solution for this problem (regardless of whether this solution is optimal or not). To see why, proceed by reduction. Suppose that you could actually find a solution for your problem in polynomial time using a greedy approach. Then, you could use your algorithm to solve in polynomial time the decision version of the Bin packing problem, which is known to be NP-complete (and, therefore, unlikely to be solvable in polynomial time).

How does this reduction work?

The decision version of the Bin packing problem involves deciding whether a certain number of bins (for example, 9) is optimal. If your hypothetical polynomial-time greedy algorithm finded a solution for 9 bins and failed to find a solution for 8 bins, then the answer for the decision problem would definitely be yes, and no otherwise.

Greedy is actually good.

All that being said, to obtain an approximate solution, a greedy approach is, probably, the best heuristic: sort the items in decreasing order of size and insert them one by one into the first bin that has room for it. This heuristic is called first-fit decreasing. The main appeal of this heuristic is that we pack the big items first and hope that the little ones fill up the spaces.

$\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.