使用位掩码+DP将数组分成K个子集，使得所有子集的总和相同

Question

所以，这个问题我不知道如何解决问题陈述是：

Given a set S of N integers the task is decide if it is possible to divide them into K non-empty subsets such that the sum of elements in every of the K subsets is equal.

N最多可以有20个。K最多可以有8个

问题具体使用DP+Bitmasks解决！

我不知道从哪里开始！由于要维护 K 个集合，我不能采用 K 个状态，每个状态代表一些或另一个！

如果我尝试将整个集合作为一个状态，将 K 作为另一个状态，我在创建循环关系时会遇到问题！

你能帮忙吗？？

原题linkProblem

Answer 1

UPD：我把 N 和 K 弄混了，我的想法是正确的，但不是 efficient.Efficient 最后添加的想法

假设到目前为止您已经创建了 k-1 个子集，现在您想要创建第 k 个子集。要创建第 k 个子集，您需要能够回答以下两个问题：

1-第k个子集的元素之和应该是多少？

2- 到目前为止使用了哪些元素？

第一个问题的答案很简单，总和应该等于所有元素的总和除以K，我们命名为subSum.

对于第二个问题，我们需要知道每个元素的状态，使用与否。这里就需要用到位掩码思路了。

这是 dp 循环：

dp[i][mask] = 表示是否可以创建 i 个子集，每个子集的总和等于 subSum，使用 1（未使用）的元素掩码（以其位表示），因此 dp[i][mask] 是布尔类型。

dp[i][mask] = OR(dp[i-1][mask2]) 对于所有可能的 mask2 状态。 mask2 将通过将掩码的某些 1 转换为 0 来生成，即我们希望成为第 i 个子集的元素的那些 1。

为了检查所有可能的 mask2，你需要检查可用 1 的所有 2^n 个可能的子集 bits.Therefore，总的来说，时间复杂度将是 O(N*(2^n)*(2^ n)).在你的问题中是 20*2^8*2^8= 10*2^17 < 10^7 可以通过时间限制。

显然，对于基本情况，您必须自己处理 dp[0][mask]，而不使用 recurrence.Final 答案是 dp[K][2^N-1] 是真还是没有。

__UPD__：为了获得更好的性能，在进入DP之前，你可以用subSum[=52=之和预处理所有子集].然后，为了计算mask2，你只需要遍历预处理后的列表，看它们与mask的AND运算是否会得到列表中的子集。

UPD2: 为了获得有效的解决方案，而不是找到合适的 mask2，我们可以利用这样一个事实，即在每一步中，我们都知道到该点为止的元素总和。所以我们可以将元素一个一个地添加到掩码中，只要我们有一个可以被 K 整除的总和，我们就可以进入下一步创建下一个子集。

if（掩码使用的元素之和能被K整除）

dp[i][mask]= dp[i+1][mask];

其他

dp[i][mask]|=dp[i][mask ^(1<<i)] provided that i-th item is not used and can not exceed the current sum more than i*subSum.

Answer 2

这是 JavaScript 中的工作 O(K*2^N*N) 实现。来自伪代码https://discuss.codechef.com/questions/58420/sanskar-editorial

http://jsfiddle.net/d7q4o0nj/

function equality(set, size, count) {
    if(size < count) { return false; }
    var total = set.reduce(function(p, c) { return p + c; }, 0);
    if((total % count) !== 0) { return false }
    var subsetTotal = total / count;
    var search = {0: true};
    var nextSearch = {};
    for(var i=0; i<count; i++) {
        for(var bits=0; bits < (1 << size); bits++){
            if(search[bits] !== true) { continue; }
            var sum = 0;
            for(var j=0; j < size; j++) {
                if((bits & (1 << j)) !== 0) { sum += set[j]; }
            }
            sum -= i * subsetTotal;
            for(var j=0; j < size; j++) {
                if((bits & (1 << j)) !== 0) { continue; }
                var testBits = bits | (1 << j);
                var tmpTotal = sum + set[j];
                if(tmpTotal == subsetTotal) { nextSearch[testBits] = true; }
                else if(tmpTotal < subsetTotal) { search[testBits] = true; }
            }            
        }
        search = nextSearch;
        nextSearch = {};
    }
    if(search[(1 << size) - 1] === true) {
        return true;
    }
    return false;
}

console.log(true, equality([1,2,3,1,2,3], 6, 2));
console.log(true, equality([1, 2, 4, 5, 6], 5, 3));
console.log(true, equality([10,20,10,20,10,20,10,20,10,20], 10, 5));
console.log(false, equality([1,2,4,5,7], 5, 3));

EDIT 该算法找到所有满足条件（总和 tmpTotal小于或等于理想子集总和subsetTotal）。按所需的子集数量 count 重复此过程，你要么有一个位掩码，其中设置了所有 size 位，这意味着成功或测试失败。

示例

设置 = [1, 2, 1, 2]

大小 = 4

count = 2，我们想尝试将集合分成2个子集

子集总数 = (1+2+1+2) / 2 = 3

迭代 1：

搜索 = {0b：正确，1b：正确，10b：正确，100b：正确，1000b：正确，101b：正确}

nextSearch = {11b：正确，1100b：正确，110b：正确，1001b：正确}

迭代 2：

搜索 = {11b：正确，1100b：正确，110b：正确，1001b：正确，111b：正确，1101b：正确}

nextSearch = {1111b: true}

最终检查

(1 << 尺寸) == 10000b, (1 << 尺寸) - 1 == 1111b

由于 nextSearch[1111b] 存在，我们 return 成功。

Answer 3

你可以在O(N * 2^N)中解决这个问题，所以K对于复杂度来说是没有意义的。

首先让我警告你所有数字都为零的极端情况 N < K，其中答案是 "no"。

我的算法思路如下。假设我们已经计算了每个掩码的总和（可以在 O(2^N) 中完成）。我们知道对于每一组，总和应该是总和除以K。

我们可以做一个带有掩码的 DP，其中状态只是一个二进制掩码，告诉已经使用了哪些数字。从算法复杂性中移除 K 的关键思想是注意到如果我们知道使用了哪些数字，我们就知道到目前为止的总和，所以我们也知道我们现在正在填充哪个组（当前总和/组总和）。然后尝试select组的下一个数字：如果我们不超过组预期总和，它将有效。

你可以查看我的C++代码：

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

typedef long long ll;

ll v[21 + 5];
ll sum[(1 << 21) + 5];
ll group_sum;
int n, k;

void compute_sums(int position, ll current_sum, int mask)
{
    if (position == -1)
    {
        sum[mask] = current_sum;
        return;
    }

    compute_sums(position - 1, current_sum, mask << 1);
    compute_sums(position - 1, current_sum + v[position], (mask << 1) + 1);
}

void solve_case()
{
    cin >> n >> k;

    for (int i = 0; i < n; ++i)
        cin >> v[i];

    memset(sum, 0, sizeof(sum));
    compute_sums(n - 1, 0, 0);

    group_sum = sum[(1 << n) - 1];
    if (group_sum % k != 0)
    {
        cout << "no" << endl;
        return;
    }
    if (group_sum == 0)
    {
        if (n >= k)
            cout << "yes" << endl;
        else
            cout << "no" << endl;
        return;
    }

    group_sum /= k;

    vector<int> M(1 << n, 0);
    M[0] = 1;
    for (int mask = 0; mask < (1 << n); ++mask)
    {
        if (M[mask])
        {
            int current_group = sum[mask] / group_sum;
            for (int i = 0; i < n; ++i)
            {
                if ((mask >> i) & 1)
                    continue;
                if (sum[mask | (1 << i)] <= group_sum * (current_group + 1))
                    M[mask | (1 << i)] = 1;
            }
        }
    }
    if (M[(1 << n) - 1])
        cout << "yes" << endl;
    else
        cout << "no" << endl;
}

int main()
{
    int cases;
    cin >> cases;
    for (int z = 1; z <= cases; ++z)
        solve_case();
}

使用位掩码+DP将数组分成K个子集，使得所有子集的总和相同

Dividing an array into K subsets such that sum of all subsets is same using bitmasks+DP

language-agnostic

algorithm

dynamic-programming