Использование алгоритма разбиения
Задано множество X = {x1, x2, …, xn} целых положительных чисел и число S. Требуется узнать, может ли число S быть представлено как сумма некоторых из чисел множества X, если каждое число можно использовать не более чем по одному разу. Только изучаю алгоритмы, и вот такое задание попалось, единственное что я понял, нужно работать с алгоритмом разбиения. Буду благодарен за любую помощь
Ответы (2 шт):
Это классическая задача на темы Meet in the Middlе, идея состоит в том, чтобы разбить данное множества на два подмножества примерно одинакового размера, и посчитать суммы представленные для каждого подмножества, стоит заметить что асимптотика такого метода намного быстрее обычного перебора, так как обычный перебор занимает 2^n(нам надо перебрать все подмножества), тогда как Meet in the Middle позволяет добиться асимптотики в sqrt(2^n), или 2^(n/2), что намного быстрее изначальной асимптотики, так как разумные ограничения первой это - n=20, а для второй n = 40. Подробнее об этом методе можно прочитать здесь, там практически такая же задача, с правильной реализацией. Такая же задача как у вас представлена на CSES, если вдруг нужно будет проверить реализацию.
Если данные такие, что S не слишком велико, то можно воспользоваться динамическим программированием. Метод работает за O(S*length(X))
Сумму i можно составить из текущего значения x и уже имеющейся (если она есть) суммы A[i-x]. Цикл в обратном порядке позволяет избежать неоднократного использования элемента в сумме.
int X[] = {2,7,13,17,23,31};
int S = 40;
std::vector<int> A(S + 1);
A[0] = 1;
for (int x : X) {
for (int i = S; i >= x; i--) {
if (A[i - x])
A[i] = 1;
}
}
if (A[S])
std::cout << S << " sum possible";