将子集和减少到 Polyomino Packing
Reduce Subset Sum to Polyomino Packing
这是一项家庭作业，如有任何帮助，我们将不胜感激。
我要证明下面的问题是NP完全的。提示说你应该将子集求和问题归约到这个问题。
Given a set of shapes, like the below, and an m-by-n board, decide whether is it possible to cover the board fully with all the shapes. Note that the shapes may not rotate.
For example, for a 3-by-5 board and the following pieces, the board can be covered like this:
现在需要注意的重要一点是，我们试图减少的子集和问题应该根据 m 和 n[ 给出输入长度多项式=21=].
任何关于使用另一个 NP 完全问题的想法都将受到赞赏。
最容易减少的是分区问题。
假设我们有一组总和为 2n 的正数，我们想知道其中的一个子集总和为 n。
我们创建一组长度为数字、宽度为 1 的块，然后尝试将它们放入宽度为 2、长度为 n 的矩形中。当且仅当分区问题对于这些数字是可解的并且行是分区时，我们才能成功。因此，任何分区问题都可以在线性时间内简化为 polyomino 打包问题。由于分区问题是NP完全的，所以我们完成了。
但是他们说的是子集和。如果他们指的是正数的子集和，那么我们可以使用另一个技巧。假设我们的数字总和为 n，并且我们想知道子集总和是否为 k。那么我们就在大小k+1和大小n-k+1的问题上加上2个数来解决分区问题。如果我们成功了，我们额外的 2 个数字就不会在同一个分区中，所以剩下的就是分区问题的解决方案。由于我们已经将分区问题简化为 polyomino 打包问题，所以我们完成了。
如果他们打算从既可以是正数也可以是负数的数字中得出子集总和，那么我看不到他们建议的减少。但由于我已经设法将 2 个著名的 NP 完全问题减少到这个问题，我认为我们很好。
这是一项家庭作业，如有任何帮助，我们将不胜感激。
我要证明下面的问题是NP完全的。提示说你应该将子集求和问题归约到这个问题。
Given a set of shapes, like the below, and an m-by-n board, decide whether is it possible to cover the board fully with all the shapes. Note that the shapes may not rotate.
For example, for a 3-by-5 board and the following pieces, the board can be covered like this:
现在需要注意的重要一点是，我们试图减少的子集和问题应该根据 m 和 n[ 给出输入长度多项式=21=].
任何关于使用另一个 NP 完全问题的想法都将受到赞赏。
最容易减少的是分区问题。
假设我们有一组总和为 2n 的正数，我们想知道其中的一个子集总和为 n。
我们创建一组长度为数字、宽度为 1 的块，然后尝试将它们放入宽度为 2、长度为 n 的矩形中。当且仅当分区问题对于这些数字是可解的并且行是分区时，我们才能成功。因此，任何分区问题都可以在线性时间内简化为 polyomino 打包问题。由于分区问题是NP完全的，所以我们完成了。
但是他们说的是子集和。如果他们指的是正数的子集和，那么我们可以使用另一个技巧。假设我们的数字总和为 n，并且我们想知道子集总和是否为 k。那么我们就在大小k+1和大小n-k+1的问题上加上2个数来解决分区问题。如果我们成功了，我们额外的 2 个数字就不会在同一个分区中，所以剩下的就是分区问题的解决方案。由于我们已经将分区问题简化为 polyomino 打包问题，所以我们完成了。
如果他们打算从既可以是正数也可以是负数的数字中得出子集总和，那么我看不到他们建议的减少。但由于我已经设法将 2 个著名的 NP 完全问题减少到这个问题，我认为我们很好。