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

Question

Given a set of non-negative distinct integers, and a value m, determine if there is a subset of the given set with sum divisible by m.

Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains an integer N and M where N denotes the size of the array and M is the number for which we have to check the divisibility. The second line of each test case contains N space separated integers denoting elements of the array A[ ].

Output: If there is a subset which is divisible by M print '1' else print '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 ("Time Limit Exceeded")。我在这个备忘录中做错了什么？

#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

不需要value。一旦你找到一个有效的组合，即如果 find_it 曾经 returns true，你可以立即 return 在所有递归调用中为真。

一些补充说明：

您应该使用一致的缩进。
int a[n] 中的可变大小数组不是标准的 C++，不适用于所有编译器。
没有理由将 m 作为 int& 而不是 int。
A map 采用布尔值与 set 相同，其中假设元素映射到 true 如果它在集合中，如果它是 false它不是。考虑使用 unordered_set 而不是 unordered_map.
像这样组合两个 unordered_map 是很昂贵的。您可以轻松地将两个键放入 std::pair 并将其用作键。这将避免维护地图的开销。
bits/stdc++.h 也是非标准的，您应该指定正确的头文件，例如#include <unordered_map> 和 #include <iostream>.
你应该在变量类型和它的名字之间放置空格，即使模板参数中的 > 允许它在没有的情况下也能正确解析。它使代码难以阅读。

Answer 2

嗯，首先，你可以将问题简化为 modulo m 问题，因为整数的属性在切换时不会改变到 modulo m 字段。很容易证明被 m 整除等同于 0 mod m.

我会首先将所有这些数字转换为它们的对应数字 modulo m 并通过考虑 a_i、[=17 来消除重复=], 3*a_i,... 直到 rep_a_i * a_i, 全部 mod m。最后你得到一个最多有 m 个元素的缩减集。然后消除那里的所有零，因为它们对总和没有贡献。这很重要，原因有二：

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

问题的其余部分是 Knapsack problem（即 NP-complete）或其中之一的 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 即 0mod 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，你知道 a priori 有一个这样的总和（在这种情况下你得到的是包括两个 4，对于原始列表的4 和 12 个数字。

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

Reduce subsequence problem complexity from exponential to polynomial?

c++

memoization

subset-sum

编辑