Given 2d dimensions and values for each items. Find maximum value you can get by filling in items in-CodePudding

This sounds very similar to knapsack or bin packing problem but I do not know how to approach it. The items are given 2d dimensions (width and height) instead of weights.

Ex. 
container: 10 x 10

items: [
    w: 3, h: 5, value: 160,
    w: 5, h: 5, value: 250,
    w: 2, h: 5, value: 150,
    w: 2, h: 3, value: 10,
]

constraints:
- items are rectangles (not necessarily squares)
- can use same items more than once
- n <= 20

Tried solving it using greedy approach, filling up the container with highest value per square area first. However, this doesn't always result in max profit.

CodePudding user response：

This can be formulated as a Mixed-Integer Programming (MIP) problem.

I tried this out: I assumed integer lengths and widths. Basically, use as decision variables:

 x(k,i,j) = 1 if item k is placed at cell (i,j)
            0 otherwise

I used the convention that "placing at (i,j)" is about the left-upper corner of the item (see the display below). Then for each cell (i',j') we require that only one item can cover it. That is a bit of a complex constraint:

 sum((i,j)|covered(k,i,j,i',j'), x(k,i,j)) <= 1   for all (i',j')

where covered(k,i,j,i',j') indicates if cell (i',j') is covered by item k if it is placed at cell (i,j).

Then the objective is

  max sum((k,i,j)|ok(k,i,j), x(k,i,j)*value(k))

here ok(k,i,j) indicates if item k can be placed at cell (i,j).

I tried this with your example. The results are:

----     74 VARIABLE x.L  item k is placed at (i,j)

            r1.c1       r1.c3       r1.c5       r1.c7       r4.c1       r6.c3       r6.c5       r6.c7

item3                       1           1           1           1
item4           1                                                           1           1           1


----     74 VARIABLE totalValue.L          =      640.000  objective (maximized)

----     79 PARAMETER occupy  items occupy cells

            c1          c2          c3          c4          c5          c6          c7          c8

r1           4           4           3           3           3           3           3           3
r2           4           4           3           3           3           3           3           3
r3           4           4           3           3           3           3           3           3
r4           3           3           3           3           3           3           3           3
r5           3           3           3           3           3           3           3           3
r6           3           3           4           4           4           4           4           4
r7           3           3           4           4           4           4           4           4
r8           3           3           4           4           4           4           4           4

Obviously, this is not completely trivial.