Problem link - CSES - Apple Division
Algorithm(s) - Complete Search with Subsets, Complete Search with Recursion
Time complexity - O(2n)
more Information - Complete Search with Recursion · USACO Guide
Short Editorial
Generate all possible subsets of apples and calculate the difference in weights of apples that are in the subset and the ones that are not.
Detailed Editorial
There are n (n <= 20) apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.
This problem can be solved by generating all possible subsets and calculating the difference in weights of apples that are in the subset and the ones that are not. The answer is the minimum of these differences.
There are 2 ways of generating all possible subsets.
1. Using recursion
2. Using bitmasks
Please note that generating subsets is much more efficient than generating permutations. We do not need permutations since order of apples in the groups is not important, only the total weight of the groups is important.
1. Using recursion
In this solution, we define a function that takes 3 arguments, number of apples, weight of group 1 and weight of group 2 and returns an integer. If the first parameter is same as the number of apples, the function returns the difference between the weights of the groups. If the value of the first parameter is less than number of apples, it recursively calls itself 2 times, first by adding the next apple to group 1 and then by adding the same apple to group 2 and then returns the minimum of the return values of these function calls as the return values.
The recursion starts by calling the function with base case (all parameters as 0) since we will be starting with empty groups with 0 weights.
Line by line editorial
long long diff(int i, long long w1, long long w2){
Recursive function with 3 parameters (number of apples, weight of group 1, weight of group 2).
if(i==n)
return abs(w1-w2);
Exit condition for the recursive call. The recursion will stop when number of apples added to the two groups equals the total number of apples to be divided
return min(diff(i+1,w1+weights[i],w2),diff(i+1,w1,w2+weights[i]));
Recursive call in case i < n. In this call, function calls itself 2 times. In first call, ith apple is added to group 1 and in second call it is added to group 2. The line returns minimum of the return values of these two recursive calls.
This recursive call will generate all the possible subsets and will always choose the most optimum subset that has the lowest weight between the two groups.
cout << diff(0,0,0) << '\n';
Initial call the recursive function with base case parameters. Base case is an empty groups of apple with 0 weights.
Complete Code (Recursion)
#include<bits/stdc++.h>
using namespace std;
int n;
int weights[20];
long long diff(int i, long long w1, long long w2){
if(i==n)
return abs(w1-w2);
else
return min(diff(i+1,w1+weights[i],w2),diff(i+1,w1,w2+weights[i]));
}
int main(){
cin >> n;
for(int i=0;i<n;i++) cin >> weights[i];
cout << diff(0,0,0) << '\n';
}
2. Using Bitmasks
Another efficient way to generate subsets is using bit representation of integers. This technique can be used to generate subsets when size of the set is less than or equal to 32 since an int in c++ has a size of 4 bytes or 32 bits. We can also use long long but the resulting number of subsets will be too large and will not fir time limit of most competitions.
Each bit of the integer can either be 0 or 1 indicating if the corresponding item in the set is part of the subset (bit = 1) or not (bit = 0). First item of the set is represented by the rightmost bit of the number, second item of the set is represented by second bit from right and so on.
To solve this problem, we generate all possible subsets and then calculate weight of apples in the subset and weight of apples not in the subset. We can then calculate the difference between the two. Final answer will be the minimum of these differences values.
Line by line editorial
for(int b = 0; b < (1 << n); b++){
A loop that goes over all the subsets. A set of size n will have 2n subsets. We use the left shift operator to get the value of 2n i.e. 1 << n = 2n
if(b & (1 << i)){
Check if an apple belongs to the subset. Binary and (&) operator is used to check if apple at index i in the set is part of the subset represented by integer b.
Complete Code (Bitmask)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> weights(n);
vector<long long> subset_weights(1 << n);
long long total_weight = 0;
for(int i = 0; i < n; i++){
cin >> weights[i];
total_weight += weights[i];
}
long long ans = LONG_MAX;
for(int b = 0; b < (1 << n); b++){
long long w1 = 0;
for(int i = 0; i < n; i++){
if(b & (1 << i)){
w1 += weights[i];
}
}
long long w2 = total_weight - w1;
ans = min(ans, abs(w1-w2));
}
cout << ans << endl;
return 0;
}
No comments:
Post a Comment