Problem 77: Balanced Partition Problem
Problem Statement: Given an array of integers, partition them into two subsets such that the absolute difference of their sums is minimized.
Input
The first line contains an integer n. The second line contains n space-separated integers.
Output
Print the minimum absolute difference between the sums of the two partitions.
Examples
Input:
4
1 6 11 5
Output:
1
Solution Explanation
Use dynamic programming to detect all possible subset sums. The answer is the minimum of |total_sum - 2*subset_sum| where subset_sum is no larger than total_sum/2.
Solution in C++
#include
#include
#include
using namespace std;
int main(){
int n;
cin >> n;
vector a(n);
int total = 0;
for(int i = 0; i < n; i++){
cin >> a[i];
total += a[i];
}
vector dp(total + 1, false);
dp[0] = true;
for(int x : a){
for(int s = total; s >= x; s--){
dp[s] = dp[s] || dp[s - x];
}
}
int ans = total;
for(int s = 0; s <= total / 2; s++){
if(dp[s]) ans = min(ans, total - 2 * s);
}
cout << ans << "\n";
return 0;
}