将子集和减少到多项式包装

Question

这是一个家庭作业，所以任何帮助表示赞赏。

我应该证明以下问题是NP完全的。提示说你应该将子集和问题减少到这个问题。

给定一组形状（如下所示）和一个m × n 的板，决定是否可以用所有形状完全覆盖板。请注意，形状可能不会旋转。

例如，对于 3×5 板和以下部件，板可以像这样覆盖：

现在需要注意的重要一点是，我们试图减少的子集和问题应该根据m和n给出输入长度多项式。

任何使用另一个 NP 完全问题的想法表示赞赏。

Answer 1

最简单的减少是来自分区问题。

假设我们有一组正数，其总和为2n，并且我们想知道其中的子集总和为n。

我们创建一组长度为数字、宽度为 1 的块，然后尝试将它们放入宽度为 2、长度为 的矩形中n。当且仅当分区问题对于这些数字是可解的并且行就是分区时，我们才能成功。因此，任何分配问题都可以在线性时间内简化为多骨牌堆积问题。由于划分问题是 NP 完全问题，我们就完成了。

但他们说的是子集总和。如果它们意味着正数的子集和，那么我们可以使用另一个技巧。假设我们的数字总和为 ，n并且我们想知道子集总和是否为k。k+1然后我们只需将2个数字添加到大小和大小的问题中n-k+1，旨在解决分区问题。如果我们成功了，我们额外的 2 个数字就不可能位于同一个分区中，因此其余的就是分区问题的解决方案。由于我们已经将分配问题简化为多联骨牌堆积问题，所以我们已经完成了。

如果他们打算从既可以是正数也可以是负数的数字中求子集总和，那么我看不到他们建议的减少。但由于我已经成功地将 2 个著名的 NP 完全问题简化为这个问题，我认为我们做得很好。