Dividing an array into K subsets in such a way that the sum of all subsets is the same using bitmask + DP

Question

So this problem, I do not know how to solve it:

Given a set S of N integers, the problem decides whether it is possible to divide them into K nonempty subsets such that the sum of the elements from each of K subsets is equal.

N can be at max 20. K can be at max 8

The problem must be solved specifically using DP + bitmax!

I can’t figure out where to start! Since there are K-sets that are supported, I cannot accept K-states representing some or others !!

If I try to take the whole set as a state and K as another, I am having problems creating a recursive relation!

Can you help?

Link to Original Problem Problem

Answer 1

This runs a working implementation of O (K * 2 ^ N * N) in JavaScript. From the pseudocode 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)); 

The EDIT Algorithm finds all bitmasks (which are bits of the subset) that match the criteria (with the sum of tmpTotal less than or equal to the ideal subset of the sum of the subset). Repeating this process by the number of subsets required for counting, you either have a bitmask where all the bits of the size are set, which means success, or test failure.

Example

set = [1, 2, 1, 2]

size = 4

count = 2, we want to try to split the set into 2 subsets

subsetTotal = (1 + 2 + 1 + 2) / 2 = 3

Iteration 1:

search = {0b: true, 1b: true, 10b: true, 100b: true, 1000b: true, 101b: true}

nextSearch = {11b: true, 1100b: true, 110b: true, 1001b: true}

Iteration 2:

search = {11b: true, 1100b: true, 110b: true, 1001b: true, 111b: true, 1101b: true}

nextSearch = {1111b: true}

Final inspection

(1 <size) == 10000b, (1 <size) - 1 == 1111b

Since nextSearch [1111b] exists, we return success.

Answer 2

You can solve the problem in O (N * 2 ^ N), so K doesn't make sense for complexity.

First, let me warn you about the angular housing N <K with all numbers equal to zero, in which the answer is "no."

The idea of ​​my algorithm is as follows. Suppose we calculated the sum of each of the masks (which can be done in O (2 ^ N)). We know that for each of the groups the sum should be the sum divided by K.

We can do DP with masks in which the state is just a binary mask indicating which numbers were used. The basic idea of ​​removing K from the complexity of the algorithm notes that if we know which numbers were used, we know the amount so far, so we also know which group we are filling now (the current amount / amount of the group). Then just try to choose the next number for the group: it will be valid if we do not exceed the expected amount of the group.

You can check my C ++ code:

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

Answer 3

UPD: I confuse N and K with each other, and my idea is true, but not effective. Effective idea added at the end.

Suppose you created k-1 subsets, and now you want to create the k-th subset. To create the kth subset, you must be able to answer these two questions:

1- What should be the sum of the elements of the kth subset?

2- What items have been used so far?

The answer to the first question is easy, the sum should be equal to the sum of all elements divided by K, call it subSum .

In the second question, we need to have the state of each element, used or not. Here we need to use the idea of ​​a bit mask.

Here's the dp repeat:

dp [i] [mask] = means that I can create subsets with the sum of each of them equal to subSum , using elements that are 1 (not used) in the mask (in its bit representation), therefore dp [i] [mask] is boolean type.

dp [i] [mask] = OR (dp [i-1] [mask2]) for all possible states of mask2 . mask2 will be produced by converting some 1 mask to 0, i.e. those 1 that we want to be elements of the i-th subset.

To test all possible mask 2 you need to check all 2 ^ n possible subsets of the available 1 bits. Therefore, to summarize, the time complexity will be O (N * (2 ^ n) * (2 ^ n)). In your task, 20 * 2 ^ 8 * 2 ^ 8 = 10 * 2 ^ 17 <10 ^ 7, which may pass the deadline.

Obviously, for the base case, you should handle dp [0] [mask] yourself, without using repetition. The true answer is whether dp [K] [2 ^ N-1] is true or not.

__ UPD __ . To get better performance, before you get into DP, you can pre-process all subsets with the sum of subSum . Then, to calculate mask2, you just need to iterate over the pre-processed list and see if the AND operation will lead to the mask in a subset of the list or not.

UPD2: In order to have an effective solution, instead of finding a suitable mask2, we could use the fact that at each step we know the sum of the elements to this point. That way, we could add elements one by one to the mask, and whenever we had a sum that is divisible by K , we could go on to the next step to create the next subset.

if (the sum of the mask elements used is divided by K)

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

yet

  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.