Блог

Это звучит очень похоже на проблему с упаковкой рюкзака или корзины, но я не знаю, как к ней подойти. Элементам задаются 2d-размеры (ширина и высота) вместо веса.

 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
 

Попробовал решить ее с помощью жадного подхода, сначала заполнив контейнер наибольшим значением на квадратную площадь. Однако это не всегда приводит к максимальной прибыли.

Это можно сформулировать как задачу смешанного целочисленного программирования (MIP).

Я попробовал это: я предположил целочисленные длины и ширины. В основном, используйте в качестве переменных принятия решений:

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

Я использовал соглашение о том,что «размещение в (i, j)» относится к левому верхнему углу элемента (см. Дисплей ниже). Затем для каждой ячейки (i’,j’) мы требуем, чтобы только один элемент мог ее покрыть. Это немного сложное ограничение:

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

где covered(k,i,j,i',j') указывает,покрывается ли ячейка (i’, j’) элементом k, если она помещена в ячейку (i, j).

Тогда цель состоит в том, чтобы

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

здесь ok(k,i,j) указывается, можно ли поместить элемент k в ячейку (i,j).

Я попробовал это на твоем примере. Результаты таковы:

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

Очевидно, что это не совсем тривиально.