Hdu 3765 Celebrity Split - 喵呜的Blog - 博客频道 - CSDN.NET

Hdu 3765 Celebrity Split - 喵呜的Blog - 博客频道 - CSDN.NET

Jack and Jill have decided to separate and divide their property equally. Each of their N mansions has a value between 1,000,000 and 40,000,000 dollars. Jack will receive some of the mansions; Jill will receive some of the mansions; the remaining mansions will be sold, and the proceeds split equally.

Neither Jack nor Jill can tolerate the other receiving property with higher total value. The sum of the values of the mansions Jack receives must be equal to the sum of the values of the mansions Jill receives. So long as the value that each receives is equal, Jack and Jill would like each to receive property of the highest possible value.

Given the values of N mansions, compute the value of the mansions that must be sold so that the rest may be divided so as to satisfy Jack and Jill.

Input

The input consists of a sequence of test cases. The first line of each test case contains a single integer N, the number of mansions, which will be no more than 20. This line is followed by N lines, each giving the value of a mansion. The final line of input contains the integer zero. This line is not a test case and should not be processed.

Output

For each test case, output a line containing a single integer, the value of the mansions that must be sold so that the rest may be divided so as to satisfy Jack and Jill.

Sample Input

5 

6000000 30000000 3000000 11000000 3000000 0

Sample Output

41000000

题目大意：Jack 和 Jill 要平分 N<=20 栋房子，每栋房子有自己的价格，他们两个人得到的房子价格之和必须相等，而不一定 20 栋房子能够被两个人平分，所以如果两个人平分后剩下没有被分到的房子要拿去拍卖，而他们希望拿去拍卖的房子价格最少，问最少的价格是多少。

这个题目一看很像背包题，我似乎感觉在以前做过很多这种类型的背包题，两个人分一堆东西什么的，但是仔细想想，貌似问的问题一般是"问能否平分""假设A 拿的不少于 B 的，相对最公平的分发是神马……"呃……可能是俺孤陋寡闻了（这题如果哪位大神会背包的解法求教……）

N=20的时候其实如果枚举是可以解决的。

对于一个物品，要么给Jack ，要么给 Jill ，要么拍卖，所以可以递归求解。

1. void Divide(int p,int differ,int hav)//p为现在要拿的房子，differ为目前两个人房子价值的差距，hav为两个人共拿走的价值  
2. {  
3.     int i,j,n;  
4.     if (differ==0)  
5.     {  
6.         if (hav>ans) ans=hav;  
7.     }  
8.     if (p<0) return;  
9.     if (abs(differ)>sum[p]) return;//剪枝1：如果两个人拿到的差距比剩下的所有房子之和大，返回。  
10.     if (sum[p]+hav<ans) return;//剪枝2：如果剩下的都加上还不能加到目前最大的答案ans，返回。  
11.     Divide(p-1,differ+a[p],hav+a[p]);//给其中一个人  
12.     Divide(p-1,differ-a[p],hav+a[p]);//给另一个人  
13.     Divide(p-1,differ,hav);//拿去拍卖  
14. }  
15. int Solve()  
16. {  
17.     ans=0;  
18.     Divide(n-1,0,0);  
19.     return sum[n-1]-ans;  
20. }  
21. int main()  
22. {  
23.     int i,j;  
24.     while(1)  
25.     {  
26.         scanf("%d",&n);  
27.         if (n==0) break;  
28.         for (i=0;i<n;i++)  
29.         {  
30.             scanf("%d",&a[i]);  
31.             if (i==0) sum[i]=a[i];  
32.             else sum[i]=sum[i-1]+a[i];  
33.         }  
34.         printf("%d/n",Solve());  
35.     }  
36.     return 0;  
37. }  

https://miyubai.wordpress.com/2011/02/11/hdu-3765-celebrity-split-dfs/

Read full article from Hdu 3765 Celebrity Split - 喵呜的Blog - 博客频道 - CSDN.NET