Let's say I have a set of rectangles of varying widths and heights, which cannot be rotated. I now want to fit a subset of those into a larger rectangle with a set height and width, so that the sum of the areas of the smaller rectangles is maximized.
Is there an algorithm that can help me solve this problem?
I tried looking into rectangle packing in general, but all I could find were questions about minimizing the area taken up by the rectangles.
Here is a graphical example of what I want to do:
The rectangles on the right are the aforementioned set of smaller rectangles, which I want to fit into the left one.
As I cannot possibly put all the small rectangles into the bigger one, I now have to choose an optimal subset of them, like this, for example:
Is this the best arrangement and subset of rectangles? Probably not, since there is still some space left in the bigger rectangle. In an ideal case, the would be exactly 0 space left, and the sum of the areas of the small rectangles would be equal to the area of the big rectangle. However, as this is rarely possible, I need an algorithm, that can find the best possible arrangement and subset.