Снизить сложность задачи подпоследовательности с экспоненциальной до полиномиальной?

Question

Снизить сложность задачи подпоследовательности с экспоненциальной до полиномиальной?

Учитывая набор неотрицательных различных целых чисел и значение m, определите, существует ли подмножество данного набора с суммой, кратной m.

Входные данные: Первая строка ввода содержит целое число T, обозначающее количество тестовых случаев. Затем следуют тесты T. Первая строка каждого теста содержит целое число N и M, где N обозначает размер массива, а M — число, для которого мы должны проверить делимость. Вторая строка каждого теста содержит N целых чисел, разделенных пробелами, обозначающих элементы массива A [].

Выход: Если есть подмножество, которое делится на M, выведите «1», иначе выведите «0».

Я попробовал рекурсивное решение:

#include <iostream>
#include<unordered_map>
using namespace std;

bool find_it(int a[],int &m,int n,int sum) {
if ((sum%m)==0 && sum>0)
return true;
if (n==0)
return false;
return find_it(a,m,n-1,sum) || find_it(a,m,n-1,sum-a[n-1]);
}

int main() {
int tc;
cin >> tc;
while (tc--) {
int n,m;
cin >> n >> m;
int a[n];
int sum = 0;
for (int i=0;i<n;i++) {
cin >> a[i];
sum += a[i];
}
bool answer = find_it(a,m,n,sum);
cout << answer << "\n";
}
return 0;
}

Который работает нормально и принимается, но затем я попробовал нисходящий подход и получаю TLE («Превышен лимит времени»). Что я делаю не так в этой памятке?

#include <iostream>
#include<unordered_map>
using namespace std;

bool find_it(
int a[], int &m, int n, int sum,
unordered_map<int,unordered_map<int,bool>> &value,
unordered_map<int,unordered_map<int,bool>> &visited){

if ((sum%m)==0 && sum>0)
return true;
if(n==0)
return false;

if(visited[n][sum]==true)
return value[n][sum];

bool first = false,second = false;
first = find_it(a,m,n-1,su1m,value,visited);

if(sum<a[n-1])
{
second=false;
}
else
second = find_it(a,m,n-1,sum-a[n-1],value,visited);

visited[n][sum] = true;
value[n][sum] = first || second;
return value[n][sum];
}

int main() {
int tc;
cin >> tc;
while (tc--) {
int n,m;
cin >> n >> m;
int a[n];
int sum = 0;
for (int i=0;i<n;i++) {
cin >> a[i];
sum+=a[i];
}
unordered_map<int,unordered_map<int,bool>> value;
unordered_map<int,unordered_map<int,bool>> visited;
cout << find_it(a,m,n,sum,value,visited) << "\n";
}
return 0;
}

0

c++memoization subset-sum

Решение

Другие решения

Ну, во-первых, вы можете уменьшить проблему до по модулю m проблема, так как свойства целых чисел не меняются при переключении на по модулю m поле. Легко показать, что делится на m то же самое, что быть идентичным 0 модификация m.

Я бы сначала преобразовал все эти числа в их аналоги по модулю m и устранить повторения, учитывая a_i, 2*a_i, 3*a_i,… до тех пор rep_a_i * a_i, все они модификация m. Наконец, вы получаете сокращенный набор, который имеет максимум m элементы. Затем удалите все нули там, поскольку они не вносят вклад в сумму. Это важно по двум причинам:

Это преобразует вашу проблему из проблемы рюкзака (NP-полной) на котором сложность O(a^n) в O(K) проблема, так как ее сложность зависит не от количества элементов множества, а от количества m,
Вы все еще можете иметь большой набор чисел для вычисления. Вы можете рассмотреть задачу о ранце с уменьшенным множеством и попытаться проверить (и дополнительно уменьшить ее) на проблему с легким ранцем (та, в которой разные значения a_i следовать геометрической последовательности с K > 2)

Остальная часть проблемы Проблема с рюкзаком (который NP-полной) или один из п варианты.

В случае, если вы не доберетесь так далеко (не можете свести это к проблеме простой рюкзака), тогда вам нужно уменьшить количество a_iвот так экспоненциальное время получает минимальную экспоненту 🙂

(@mss просит уточнения в комментарии) Предположим, у вас есть m = 8 и список 1 2 4 6 12 14 22, После снижения модификация m список остается в виде: 1 2 4 6 4 6 6 в котором 6 повторяется три раза. мы должны рассмотреть три возможных повторения 6, поскольку они могут способствовать получению суммы, но не более (на данный момент), давайте рассмотрим 6*1 = 6, 6*2 = 12 а также 6*3 = 18во-первых, оригинал 6вторая делает третье повторение 4 (поэтому мы должны рассмотреть 3 4s в списке), а третий превращается в 2, Итак, теперь у нас есть 1 2 4 6 4 4 2 в списке. Мы делаем то же самое для 4 повторы (два 4 наткнуться на 8 который 0модификация m и не вносить вклад в суммы, но мы должны держать один такой 0 потому что это означает, что вы получили по повторным номерам цель m) получить в 1 2 4 6 0 4 2 => 1 2 4 6 0 0 2 = (Переупор) => 0 1 2 2 4 6 => 0 1 2 4 6, Это должен быть окончательный список для рассмотрения. Как это имеет 0, ты знаешь априори что есть одна такая сумма (в этом случае вы получаете, как в том числе два 4, для оригинального списка 4 а также 12 номера.

0

Источник

Accepted Answer

Там нет необходимости value, Как только вы найдете правильную комбинацию, то есть, если find_it когда-либо возвращается true, вы можете просто немедленно вернуть true во всех рекурсивных вызовах.

Некоторые дополнительные замечания:

Вы должны использовать последовательный отступ.
Массивы переменного размера как в int a[n] не являются стандартными C ++ и не будут работать на всех компиляторах.
Нет причин проходить m как int& вместо int,
map принимая булевы значения так же, как set где элемент должен отображаться в true если это в наборе и false если это не так. Рассмотреть возможность использования unordered_set вместо unordered_map,
Сочинять два unordered_mapКак это дорого. Вы можете так же легко положить оба ключа в std::pair и используйте это как ключ. Это позволило бы избежать накладных расходов по обслуживанию карты.
bits/stdc++.h также является нестандартным, и вы должны указать правильные заголовочные файлы, например, #include <unordered_map> а также #include <iostream>,
Вы должны поместить пробелы между типом переменной и ее именем, даже если > из параметра шаблона позволяет правильно анализировать без. Это делает код трудным для чтения.

1