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