HDU 1171 Big Event in HDU （母函數） Big Event in HDU

time limit: 10000/5000 ms (java/others)    memory limit: 65536/32768 k (java/others)

total submission(s): 21671    accepted submission(s): 7598

problem description

nowadays, we all know that computer college is the biggest department in hdu. but, maybe you don‘t know that computer college had ever been split into computer college and software college in 2002.

the splitting is absolutely a big event in hdu! at the same time, it is a trouble thing too. all facilities must go halves. first, all facilities are assessed, and two facilities are thought to be same if they have the same value. it is assumed that there is

n (0<n<1000) kinds of facilities (different value, different kinds).

input

input contains multiple test cases. each test case starts with a number n (0 < n <= 50 -- the total number of different facilities). the next n lines contain an integer v (0<v<=50 --value of facility) and an integer m (0<m<=100 --corresponding number of the

facilities) each. you can assume that all v are different.

a test case starting with a negative integer terminates input and this test case is not to be processed.

output

for each case, print one line containing two integers a and b which denote the value of computer college and software college will get respectively. a and b should be as equal as possible. at the same time, you should guarantee that a is not less than b.

sample input

sample output

題意：有n樣物品，每樣物品價值是v，件數是m。盡量把這些物品分成兩堆使得兩邊總價值最接近。輸出分得的兩堆各自的價值。

利用母函數法來解決，因為分成兩堆，而兩堆中較小的一堆最大為所有物品總價值量的一半，是以母函數的組合數上下就可以設定成總價值量的一半。求出所有的組合後，可以利用貪心的思想來得到答案，因為要求兩堆之差盡可能小，是以就可以從總價值量的一半開始向小的方向找，找到最大的價值量，則另一堆的價值量就是總價值量-此堆的價值量。因為組合數可能較大，這裡不記錄組合種數，而是用一個标記來表示該數能否組合出即可。