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

Question

所以,这个问题我没有任何线索如何解决它的问题陈述是:

给定N个整数的集合S,任务决定是否可以将它们划分为K个非空子集,使得每个K个子集中的元素之和相等.

N可以是最大20.K可以是最大8

问题是使用DP + Bitmasks专门解决!

我无法理解从哪里开始!由于有K套维护,我不能把K各自代表一些或另一个!

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

你能帮我吗？？

原始问题的链接问题

Answer 1

这是 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));

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

例子

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

尺寸=4

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

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

迭代 1：

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

下一个搜索= {11b：真，1100b：真，110b：真，1001b：真}

迭代 2：

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

下一个搜索= {1111b：真}

最终检查

(1 << 大小) == 10000b, (1 << 大小) - 1 == 1111b

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