代码之家 › 专栏 › 技术社区 › rosacart

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

p-np subset-sum polynomial-math algorithm

0

rosacart · 技术社区 · 9 年前

这个多项式时间的整件事让我很困惑,例如:我想用多项式时间算法编写一个程序,只从一个集合中选取4个和为0的整数。例如:假设我有以下一组整数{8,20,3,-2,3,7,16,-9}。我如何才能在多项式时间内从集合中只选取4个和为0的不同整数,而不必检查除4以外的所有可能长度?请注意,在程序中,我不需要搜索除4以外的任何其他可能长度。我的预期解是{8,3,-2,-9}=0。我完全知道我只需要集合{8、20、3、-2、3、7、16、-9}中的4个整数。

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

2 回复 | 直到 9 年前

1

0

Lingxi 9 年前

以下算法在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;
  }
}

2

0

Yves Daoust 9 年前

尝试所有四次,不要重复。这最多需要 (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    <==