Уменьшить сложность задачи подпоследовательности от экспоненциальной до полиномиальной? - PullRequest
0 голосов
/ 11 ноября 2018

Я работаю над следующей проблемой :

Учитывая набор неотрицательных различных целых чисел и значение 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;
}

Ответы [ 2 ]

0 голосов
/ 13 ноября 2018

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

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

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

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

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

редактировать

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

0 голосов
/ 11 ноября 2018

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

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

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