algorithm - 解决 'toy matching puzzle' 的最佳算法是什么？

Question

想象这样的谜题: puzzle

我有几种形状，例如:

• 10圈

• 8个三角形

• 9个正方形

我也有一些盘子用来放形状，例如:

• A板:2个圆孔，3个三角孔，1个方孔

• B板:1个圆孔，0个三角孔，3个方孔

• C板:2个圆孔，2个三角孔，2个方孔

我想找到最小数量的盘子来放置所有形状(盘子不需要完全填满)

例如:

• 我可以选择 6 个盘子 [A, A, A, B, B, C]，我可以插入所有形状

• 但我也可以选择 [A, A, C, C, C] 这也可以，

• 所以这个问题的答案是:5

如果这个问题推广到 N 型形状和 M 型板，解决这个问题的最佳算法是什么？答案的时间复杂度是多少？

Answer 1

这个问题是一个 NP-hard 问题，一旦你意识到有一个非常简单的 polynomial time reduction 就更容易看出来了来自 bin packing problem到这个问题。

我建议您使用 integer linear programming技术来解决它。

解决您问题的 ILP 可以是:

// Data
Shapes  // array of integers of size n, contains the number of each shape to fit
Plates  // 2D array of size n * m, Plates[i][j] represents the number of shape of type i
        // that fit on a plate of type j
// Decision variables
X       // array of integer of size m, will represent the number of plates of each type to use
// Constraints
For all j in 1 .. m, X[j] >= 0   // number of plates cannot be negative
For all i in 1 .. n, sum(j in 1..m) Plates[i][j] * X[j] >= Shapes[i] // all shapes must fit
Objective function:
minimize sum(j in 1..n) X[j]

在 OPL 中编写伪代码，将其提供给 linear programming solver ，考虑到此问题与装箱问题的相似性，您应该可以相当快地获得解决方案。

编辑:如果您不想经历学习 LP 基础知识、OPL、LP 求解器等的麻烦......那么解决此问题的最好和最简单的方法就是一个很好的旧方法 branch and bound这个问题的实现。分支定界法是一种非常简单而强大的算法，可用于解决范围广泛的问题....必知。