Unbounded, 2-dimensional knapsack problem

Question

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.

Answer 1

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.