解决“玩具匹配难题”的最佳算法是什么？

Question

想象一下这样的拼图：拼图

我有几种形状，例如：

• 10圈
• 8个三角形
• 9个方格

我也有一些盘子可以放置形状，例如：

• 板A:2个圆孔，3个三角形孔，1个方形孔
• 板B:1圆孔，0三角形孔，3方孔
• 板C:2个圆孔，2个三角形孔，2个方形孔

我想找到最少数量的盘子，把所有的形状(盘子不需要完全填充)

例如：

• 我可以选择6个板块A，B，B，C，我可以插入所有形状
• 但我也可以选择A，A，C，这也可以，
• 所以这个问题的答案是：

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

Answer 1

这个问题是NP难问题，一旦您意识到从多项式时间约简到这个问题有一个非常简单的装箱问题，就更容易理解它。

我建议您使用整数线性规划技术来解决这个问题。

解决您的问题的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中编写伪代码，将其提供给线性规划求解器，考虑到这个问题与装箱包装的相似性，您应该得到一个相当快的解决方案。

编辑:如果你不想通过学习LP基础的麻烦，OPL，LP解说员等.那么，解决这个问题的最好和最简单的方法就是这个问题的一个好的旧枝界实现。分支和界是一个非常简单和强大的算法，可以用来解决广泛的问题。必须知道。

Answer 2

我认为应该使用动态规划来解决这个问题。

下面是一个伪代码的解决方案(我还没有测试它，但我认为它应该能工作)：

parts = the number of shapes we want to fit as a vector
plates = the of plates we can use as a matrix (vector of vector)

function findSolution(parts, usedPlates):
    if parts < 0: //all elements < 0
        return usedPlates;
    else:
        bestSolution = null //or anything that shows that there is no solution yet
        for X in plates:
            if (parts > 0 on any index where X is > 0): //prevents an infinite loop (or stack overflow because of the recursion) that would occur using only e.g. the plate B from your question
                used = findParts(parts - X, used.add(X)); //elementwise subtraction; recursion
                if (used.length < best.length):
                    //the solution is better than the current best one
                    best = used;

        //return the best solution that was found
        return best

使用问题中的值，初始变量将是：

parts = [10, 8, 9]
plates = [[2, 3, 1], [1, 0, 3], [2, 2, 2]]

你会像这样启动这个函数：

solution = findSolution(parts /*= [10, 8, 9]*/, new empty list);
//solution would probably be [A, A, C, C, C], but also [C, C, C, C, C] would be possible (but in every case the solution has the optimal length of 5)

使用此算法，您可以使用递归将问题划分为较小的问题(这是大多数动态规划算法所做的)。

这样做的时间复杂性并不是很好，因为你必须寻找每一个可能的解决方案。根据主定理，时间复杂度应该类似于:O(n^(log_b(A)，其中n=a=使用的板数(在您的示例3中)。B(对数的基数)不能在这里计算(或者至少我不知道如何计算)，但我假设它接近1，这使它成为一个相当大的指数。但这也取决于零件向量中条目的大小和板块向量中的条目(较少的板块需要->更好的时间复杂度，而许多板块需要->坏的时间复杂度)。

所以时间复杂度不是很好。对于更大的问题，这将需要非常长的时间，但对于小问题，如你的问题，它应该有效。