algorithm - 给定 N 个包含 N 个元素的整数数组，检查是否可以通过从每个数组中取一个元素来形成 X

Question

给定 N 个包含 N 个元素的数组和一个数字 X，检查是否可以通过从每个数组中取出一个元素来形成 X。

您必须从每个数组中取 1 个且仅取 1 个元素。

对于 N = 2，我们需要找到一对可以在 O(n) 时间内完成的对(使用集合或假设数组已排序)。对于 N = 3，复杂度将为 O(n2)？

对于 N = 4，可以完成 n2Log(n) 次。

如何对 N 个数组进行泛化？

Answer 1

这看起来像是 subset sum problem 的一些变体, 并且可以使用 Dynamic Programming 类似地解决在 pseudo-polynomial时间:

D[0][0] = true
D[0][w] = false   | w != 0
D[i][w] = OR { D[i-1][w-x] | for each x in array i }

然后，您要查找D[n][X] 的值.

直觉上，您正在做的是检查 i 中的每个元素。 th 数组，并检查每个 w <= X 将您带到何处，然后递归检查是否可以实现。请注意，这里的递归是象征性的，因为动态规划不需要递归解决方案。

解的时间复杂度是O(n^2 * X) , 因为表的每个条目都需要 O(n)计算时间，有n*X表中的条目。