Minimum Subset Sum Difference
mediumDynamic Programming II+20 XPTime limit 2s
Two friends split n bags of rice with weights a[1] … a[n] kg. Every bag goes to exactly one friend (a friend may get nothing). Make the two totals as close as possible and print the smallest possible difference between them.
Input:
- line 1:
n - line 2:
nweights
Output: the minimum absolute difference of the two totals.
Constraints: 1 ≤ n ≤ 200, 1 ≤ a[i] ≤ 500.
Think about it: if one friend's total is s, the difference is |total − 2s|. So find every reachable subset sum s (a boolean subset-sum table up to total, O(n · total)), and pick the one closest to total / 2.
Sample input 1
4 1 6 11 5
Sample output 1
1
Sample input 2
2 3 3
Sample output 2
0
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).