将子序列问题的复杂度从指数级降低到多项式级？

Question

我正在研究以下问题：

给定一组非负的不同整数，并给出一个值m，确定给定集合是否有一个子集，其和可被m整除。

输入：输入的第一行包含一个整数T，表示测试用例的数量。然后是T个测试用例。每个测试用例的第一行包含一个整数N和M，其中N表示数组的大小，M是我们必须检查整除性的数字。每个测试用例的第二行包含N个空格分隔的整数，表示数组A[]的元素。

#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;
}

#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;
}

Answer 1

首先，您可以将问题简化为模M问题，因为当切换到模M字段时，整数的属性不会改变。可以很容易地证明，被m整除就等于与0modm相同。

我首先将所有这些数字转换成它们的对应模m，并通过考虑a_i，2*a_i，3*a_i，······在rep_a_i*a_i之前，它们都是modm。最后，得到一个最多包含M元素的约简集。然后消除那里所有的零，因为它们对和没有贡献。这很重要，有两个原因：

• 它将问题从复杂性为O(a^n)的背包问题（NP-complete）转换为O(K)问题，因为它的复杂性不取决于集合的元素数，而是M.
• 您仍然可以有一大组数字要计算。您可以将约简集视为背包问题，并尝试检查（并进一步约简它）易背包问题（其中不同值a_i遵循具有k>2
的几何序列）

问题的其余部分是一个背包问题（它是NP完全的）或它的一个P变体。

如果您没有做到这一点（不能将其简化为一个简单的背包问题），那么您必须减少a_i的数量，以便指数时间得到一个最小指数：）

(@MSS在评论中要求精化）假设您有M=8，列表为1 2 4 6 12 14 22。在简化modm之后，列表仍然为:1 2 4 6 4 6 6，其中6重复了三次。我们必须考虑6的三个可能的重复，因为它们可以帮助得到一个和，但不能更多（目前），让我们考虑6*1=6，6*2=12和6*3=18，第一个是原始的6，第二个对4进行第三次重复（因此我们需要在列表中考虑34)，第三个转换为2。现在，列表中有1 2 4 6 4 4 2。我们对4重复做同样的处理（两个4运行到8，这是0m，不影响和，但我们必须保留一个这样的0，因为这意味着您通过重复的数字得到目标m)进入1 2 4 6 0 2 2=>1 2 4 6 0 2=(reorder)=>0 1 2 2 4 6=>0 1 2 2 4 6这应该是最后要考虑的名单。因为它有一个0，所以您先验地知道有一个这样的和（在本例中，对于原始列表的4和12数字，您得到的是包括两个4。