Apple Division CSES Problem Set Solution | CSES Problem Set Solution Apple division with code -
Apple Division CSES Problem Solution Easy Explanation. Apple division is problem is taken form cses introductory problem set.Let's Read Problem statement first.
Problem Statement-
- Time limit: 1.00 s
- Memory limit: 512 MB
Input
The first input line has an integer : the number of apples.
The next line has integers : the weight of each apple.
Output
Print one integer: the minimum difference between the weights of the groups.
Constraints
Input:
5
3 2 7 4 1Output:
1Explanation: Group 1 has weights 2, 3 and 4 (total weight 9), and group 2 has weights 1 and 7 (total weight 8).
Join Telegram channel for code discussion- https://t.me/competitiveProgrammingDiscussion
Solution-
Apple division problem can be solved using recursion because contrain is too small so in can be done by recursion.
First we generate all subsequence of weight and which subset-sum difference is minimum we will print that ans.
For generating one subset we will use recursion for every element of array we have two choices either take it or not to take it.
let say the entire array sum is S.
and one of Subsequence sum is x so the sum of another segment of the array will be S-x . so the difference of two subsets of array is
abs((totalsum-currsum) - currsum);
currsum denote the sum of one subsequence.
so we will make recursive call now and return minimum ans
return min(findminans(arr,currsum+arr[i],totalsum,i-1),findminans(arr,currsum,totalsum,i-1));
Here is my Code-
Your English is very bad.
ReplyDeletewhy cant we just sort it ?
ReplyDelete#include
#include
#include
using namespace std;
int main() {
std::ios::sync_with_stdio(false);
int n;
cin >> n;
vector apples(n);
for(int i = 0; i < n; i++) {
cin >> apples[i];
}
sort(apples.begin(), apples.end());
int sum_a = 0, sum_b = 0;
for (int i = n-1; i >= 0; i--) {
if (sum_a <= sum_b) {
sum_a += apples[i];
} else {
sum_b += apples[i];
}
}
cout << abs(sum_a - sum_b) << endl;
return 0;
}