0

例如，关于这个多项式时间的整个事情让我感到困惑：我想用多项式时间算法编写一个程序，它只会从一组中选择 4 个总和为 0 的整数。例如：假设我有以下一组整数 {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, 3, -2, -9} 的多项式时间解，即使我仅将原始集合的长度从 8 个整数增加到 100 个整数，而我仍然必须选择总和为的 4 个元素0 但从 100 个整数的集合中，它仍然是关于输入大小的多项式快速（即用于存储输入的位数）？

4

2 回答 2

0

不重复地尝试所有四组。这最多需要(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    <==
于 2016-02-02T13:16:55.973 回答
0

以下算法在 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;
  }
}
于 2016-02-02T13:56:36.430 回答