如何从多项式时间算法中的一组中只选择 4 组整数

Question

关于这个多项式时间的整个事情让我感到困惑，例如：我想用多项式时间算法编写一个程序，它只会从一个集合中选择总和为 0 的 4 个整数。例如：假设我有以下整数集 {8, 20, 3, -2, 3, 7, 16, -9}。我如何才能在多项式时间内从集合中仅选择 4 个总和为 0 的不同整数，而无需检查除 4 以外的所有可能长度？请注意，在程序中我不需要搜索除 4 以外的任何其他可能长度。我预期的解决方案是 {8、3、-2、-9} = 0。完全清楚我只需要集合 { 中的 4 个整数8、20、3、-2、3、7、16、-9}。

编辑：即使我只将原始集合的长度从 8 个整数增加到 100 个整数，我是否会找到 {8, 3, -2, -9} 的多项式时间解，而我仍然必须选择我的4 个元素总和为 0，但从 100 个整数的集合中，相对于输入的大小（即用于存储输入的位数）它仍然是多项式快速的吗？

Answer 1

不重复地尝试所有四重奏。这最多需要 (N^4-6N³+11N²-6N)/24 次尝试，每次尝试都在恒定时间内完成。

8 + 20 + 3 - 2 = 29
8 + 20 + 3 + 3 = 34
8 + 20 + 3 + 7 = 38
8 + 20 + 3 + 16 = 47
8 + 20 + 3 - 9 = 22
8 + 20 - 2 + 3 = 29
8 + 20 - 2 + 7 = 33
8 + 20 - 2 + 16 = 42
8 + 20 - 2 - 9 = 17
8 + 20 + 3 + 7 = 38
8 + 20 + 3 + 16 = 47
8 + 20 + 3 - 9 = 22
8 + 20 + 7 + 16 = 51
8 + 20 + 7 - 9 = 26
8 + 20 + 16 - 9 = 35
8 + 3 - 2 + 3 = 12
8 + 3 - 2 + 7 = 16
8 + 3 - 2 + 16 = 25
8 + 3 - 2 - 9 = 0    <==
8 + 3 + 3 + 7 = 21
8 + 3 + 3 + 16 = 30
8 + 3 + 3 - 9 = 5
8 + 3 + 7 + 16 = 34
8 + 3 + 7 - 9 = 9
8 + 3 + 16 - 9 = 18
8 - 2 + 3 + 7 = 16
8 - 2 + 3 + 16 = 25
8 - 2 + 3 - 9 = 0    <==
8 - 2 + 7 + 16 = 29
8 - 2 + 7 - 9 = 4
8 - 2 + 16 - 9 = 13
8 + 3 + 7 + 16 = 34
8 + 3 + 7 - 9 = 9
8 + 3 + 16 - 9 = 18
8 + 7 + 16 - 9 = 22
20 + 3 - 2 + 3 = 24
20 + 3 - 2 + 7 = 28
20 + 3 - 2 + 16 = 37
20 + 3 - 2 - 9 = 12
20 + 3 + 3 + 7 = 33
20 + 3 + 3 + 16 = 42
20 + 3 + 3 - 9 = 17
20 + 3 + 7 + 16 = 46
20 + 3 + 7 - 9 = 21
20 + 3 + 16 - 9 = 30
20 - 2 + 3 + 7 = 28
20 - 2 + 3 + 16 = 37
20 - 2 + 3 - 9 = 12
20 - 2 + 7 + 16 = 41
20 - 2 + 7 - 9 = 16
20 - 2 + 16 - 9 = 25
20 + 3 + 7 + 16 = 46
20 + 3 + 7 - 9 = 21
20 + 3 + 16 - 9 = 30
20 + 7 + 16 - 9 = 34
3 - 2 + 3 + 7 = 11
3 - 2 + 3 + 16 = 20
3 - 2 + 3 - 9 = -5
3 - 2 + 7 + 16 = 24
3 - 2 + 7 - 9 = -1
3 - 2 + 16 - 9 = 8
3 + 3 + 7 + 16 = 29
3 + 3 + 7 - 9 = 4
3 + 3 + 16 - 9 = 13
3 + 7 + 16 - 9 = 17
- 2 + 3 + 7 + 16 = 24
- 2 + 3 + 7 - 9 = -1
- 2 + 3 + 16 - 9 = 8
- 2 + 7 + 16 - 9 = 12
3 + 7 + 16 - 9 = 17

更新:

应 OP 的要求，找到解决方案后停止。

8 + 20 + 3 - 2 = 29
8 + 20 + 3 + 3 = 34
8 + 20 + 3 + 7 = 38
8 + 20 + 3 + 16 = 47
8 + 20 + 3 - 9 = 22
8 + 20 - 2 + 3 = 29
8 + 20 - 2 + 7 = 33
8 + 20 - 2 + 16 = 42
8 + 20 - 2 - 9 = 17
8 + 20 + 3 + 7 = 38
8 + 20 + 3 + 16 = 47
8 + 20 + 3 - 9 = 22
8 + 20 + 7 + 16 = 51
8 + 20 + 7 - 9 = 26
8 + 20 + 16 - 9 = 35
8 + 3 - 2 + 3 = 12
8 + 3 - 2 + 7 = 16
8 + 3 - 2 + 16 = 25
8 + 3 - 2 - 9 = 0    <==

Answer 2

以下算法在 O(N^3 * logN) 中运行。

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

using quadruple = std::tuple<int, int, int, int>;

std::vector<quadruple> find(std::vector<int> vec) {
  std::sort(vec.begin(), vec.end());
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
  std::vector<quadruple> ret;
  for (auto i = 0u; i + 3 < vec.size(); ++i) {
    for (auto j = i + 1; j + 2 < vec.size(); ++j) {
      for (auto k = j + 1; k + 1 < vec.size(); ++k) {
        auto target = 0 - vec[i] - vec[j] - vec[k];
        auto it = std::lower_bound(vec.begin() + k + 1,
            vec.end(),
            target);
        if (it != vec.end() && *it == target) {
          ret.push_back(std::make_tuple(
              vec[i], vec[j], vec[k], target));
        }
      }
    }
  }
  return ret;
}

int main() {
  std::vector<int> input = {8, 20, 3, -2, 3, 7, 16, -9};
  auto output = find(input);
  for (auto& quad : output) {
    std::cout << std::get<0>(quad) << ' '
              << std::get<1>(quad) << ' '
              << std::get<2>(quad) << ' '
              << std::get<3>(quad) << std::endl;
  }
}

如何从多项式时间算法中的一组中只选择 4 组整数

How to pick only 4 set of integers from a set in polynomial time algorithm

algorithm

polynomial-math

subset-sum

p-np