给定每个项目的二维尺寸和值。通过将项目填充到 n x n 容器中找到你可以获得的最大值

Question

这听起来与背包或垃圾箱包装问题非常相似，但我不知道如何处理。这些项目被赋予二维尺寸（宽度和高度）而不是重量。

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

尝试使用贪心法解决它，先填满每平方面积价值最高的容器。然而，这并不总能带来最大利润。

Answer 1

这可以表述为混合整数规划 (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)。

那么objective就是

  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

显然，这并非完全微不足道。

给定每个项目的二维尺寸和值。通过将项目填充到 n x n 容器中找到你可以获得的最大值

Given 2d dimensions and values for each items. Find maximum value you can get by filling in items in n x n container

algorithm

knapsack-problem

linear-programming

bin-packing