I have the following problem:

There is rectangle with fixed $W > w_i$ width and $H > h_i$ height. Given a set of item types, where each type has some $w_i$ width, $h_i$ height and $v_i$ value. I would like to maximize the value of the items placed in the rectangle.

An item can be placed as many times as needed. Not every type has to be present in the optimal solution. Two items can not overlap.

Is there any literature available for this (or a similar) problem? Is there a name for this problem? I didn't have luck with finding info on optimizing inside a 2-D region.


Just the special case of (in your terms) 1-dimensional knapsack is NP-complete, and that is a special case of your 2-dimensional one (just take a strip of width one to be filled with strips of width one). It is very unlikely that an efficient algorithm exists for your problem.

Similar problems are handled e.g. by newspapers (need to fill pages with rectangles for ads, for instance), when cutting up sheets into custom sizes and similar applications. Search for those, there must be publications on approximation algorithms.

| cite | improve this answer | |

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.