Divorce
Time limit30sMemory limit128 MB
Pick two disjoint subsets of up to 24 houses with equal sums, maximizing that common sum, and report the value of the houses left out.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Bit manipulation, Brute force, Divide and conquer
- Solved
- No attempts yet
Problem
Jack and Jill are getting divorced and want to split the property they built together fairly. Together they own houses, and the value of each house is at least 1,000,000 dollars and at most 40,000,000 dollars.
Jack takes some of the houses and Jill takes some of the houses. The total value of the houses Jack takes must be exactly equal to the total value of the houses Jill takes. Every house that neither of them takes is sold.
If there are several fair ways to split the property, they choose the one that makes the value each person receives (the two values are equal) as large as possible. In other words, they make the total value of the houses that must be sold as small as possible.
Given the values of the houses, write a program that computes the total value of the houses that must be sold.
Input
The input consists of several test cases. The first line of each test case contains the number of houses , where is at most 24. Each of the next lines contains the value of one house.
The last line of the input contains a single 0, which marks the end of the input.
Output
For each test case, print on its own line the total value of the houses that must be sold in order to split the property fairly.
Hint
For example, suppose the five houses are worth 6,000,000, 30,000,000, 3,000,000, 11,000,000, and 3,000,000 dollars. If Jack takes the house worth 6,000,000 dollars and Jill takes the two houses worth 3,000,000 dollars each, then each of them receives houses worth 6,000,000 dollars in total, so the property is split fairly. The two remaining houses (worth 11,000,000 and 30,000,000 dollars) are sold, and their total value is 41,000,000 dollars.