Как выбрать только 4 набора целых чисел из набора в алгоритме с полиномиальным временем

Все дело в этом полиномиальном времени меня путает, например: я хочу написать программу в алгоритме с полиномиальным временем, который будет выбирать только 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}.Как выбрать только 4 набора целых чисел из набора в алгоритме с полиномиальным временем

Редактировать: Я нашел полиномиальное временное решение {8, 3, -2, -9}, даже если я увеличиваю только длину исходного набора от 8 до 100 целых чисел, в то время как мне все равно придется выбрать мой 4 элементы, которые суммируются до 0, но из набора из 100 целых чисел, будут ли они по-прежнему быть многочленными относительно размера ввода (т. е. количества бит, используемых для хранения ввода)?

источник

2016-02-02 rosacart

Попробуйте все отдельные четверки. Это требует не более усилий (N^4-6N³ + 11N²-6N)/24'. –

Следующий алгоритм работает в 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-02 13:56:36 Lingxi

Спасибо, я найду полиномиальное временное решение {8, 3, -2, -9}, даже если я увеличиваю только длину исходного набора от 8 до 100 целых чисел, в то время как мне все же придется выбирать мои 4 элемента, которые суммируют до 0, но из набора из 100 целых чисел будет ли он по-прежнему быть многочленным относительно размера ввода (т. е. количества бит, используемых для хранения ввода)? – rosacart

@rosacart Сложность по времени является полиномиальной по отношению к N - размеру общего набора. Так да. – Lingxi

Итак, какова будет импликация в каждой задаче суммирования сумм, если мы можем точно знать или прогнозировать фактическую длину целых чисел, суммируемых до нуля? Может ли это привести к алгоритму полиномиального времени для задачи суммирования сумм? – rosacart

Попробуйте все четвероногие без повторений. Это занимает не более (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

Update:

По просьбе ОП, прекращается, когда будет найдено решение.

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-02 13:16:55

Спасибо, я хотел бы, чтобы он немедленно остановился, он нашел первое подмножество, равное 0. Затем он должен заканчиваться после того, как найдено {8 + 3-2-9}. – rosacart

Как выбрать только 4 набора целых чисел из набора в алгоритме с полиномиальным временем

ответ

Смежные вопросы