algorithm - DP解决方案，查找是否存在一组可被M整除的数字

假设我们有n个数，使得0现在我们必须检查是否可以从数组中选择一组数字，使它们的和可以被M整除，并输出“YES”或“NO”。
下面是两个例子：
N=3，M=5a={1,2,3}回答“是”
N=4，M=6 a={3,1,1,3}回答“是”
提前谢谢。

最佳答案

C++解决方案。

//declare dp array of boolean values of size M
bool dp[M] = {0}; // init with fasle values
for(int i = 0; i < N; i++) {
    bool ndp[M] = {0}; // init temporary boolean array
    ndp[a[i] % M] = 1; // add a subset with one a[i] element
    for(int j = 0; j < M; j++)
        if(dp[j]) { // if we may find a subset of elements with sum = j (modulo M)
            ndp[j] = 1; // copy existing values
            ndp[(j + a[i]) % M] = 1; // extend the subset with a[i], which will give a sum = j + a[i] (modulo M)
        }
    // copy from ndp to dp before proceeding to the next element of a
    for(int j = 0; j < M; j++) dp[j] = ndp[j];
}

//check dp[0] for the answer

算法复杂度将是O（n*m），在你的情况下是O（109）。
编辑：添加ndp[a[i] % M] = 1;行以使dp[j]变为非零。
可能还有另一个可选的o（m*m*log（m）+n）解，在您的例子中是o（107）（但有大常数）。
注意，如果用a[i]替换每个a[i] % M，则问题语句不会更改让我们计算a[i]元素的数量，这些元素在j上除法后给出特定的余数如果对于某些余数M我们在j中发现k元素，那么我们可以生成以下子集的和（这可能产生唯一余数）
a
示例：让j, 2 * j % M, 3 * j % M ... k * j % M并且对于余数M = 6我们在2中找到5元素然后我们得到以下子集的唯一和：
a
即2 % 6, 2 * 2 % 6, 3 * 2 % 6, 4 * 2 % 6, 5 * 2 % 6
以布尔形式存储此信息0, 2, 4
最多我们有{1, 0, 1, 0, 1, 0}这样的组，它们产生M大小的布尔数组，其中包含可能的余数。
下一步，我们需要找到所有可能出现的子集，如果我们将采取不同组的元素。假设我们合并了两个bool余数数组M和a，如果我们可以引入新的数组b，它将包含c和a子集中元素的所有可能余数和。天真的方法将要求我们在b和a两个嵌套循环中给出O（m2）合并时间复杂度。
我们可以使用快速傅立叶变换ALGO降低O（m*log（m））的复杂度。每个布尔数组都有一个多项式Ai*Xi，其中系数AI取自布尔数组。如果我们想合并两个数组，我们可以把它们的多项式相乘。
总的来说是O（m2 * log（m）），因为我们需要做出这样的合并。

关于algorithm - DP解决方案，查找是否存在一组可被M整除的数字，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42734931/