d390: 00562 - Dividing coins
Tags : DP 子集和問題
Accepted rate : 599人/696人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-15 02:52

Content

很多人都知道銅線是荷蘭人發明的。聽說是有 2 個荷蘭人在爭奪一個銅幣,由於搶的太激烈,銅幣被約拉越長,最後銅線就被發明出來了。

現在,你要來幫助處理一個關於銅幣的問題。給你一袋銅幣(裡面最多有 100 個,面值可能有 1 分錢到 500 分錢,但單一銅幣是不可分割的)。若要把銅幣分成 2 堆,並且使得這 2 堆銅幣的面值和盡可能接近,你必須回答這 2 堆銅幣面值和的差是多少。

Input

輸入的第一列有一個整數

代表以下有幾組測試資料

每組測試資料 2 列

其中第一列有 1 個不為負的整數 m(m <= 100)

代表袋中銅幣的數目

接下來的一列有 m 個正整數

代表袋中各銅幣的面值

Output

對每一組測試資料

輸出 2 堆銅幣面值和的差是多少

Sample Input #1
2
3
2 3 5
4
1 2 4 6
Sample Output #1
0
1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :

* 中文翻譯:Lucky 貓 

DP (背包問題(Knapsack Problem))

相似題 : b116. TOI2008 3. 加減問題

Tags:
DP 子集和問題
出處:
UVa562 [管理者: morris1028(碼畜) ]


ID User Problem Subject Hit Post Date
28058 goodsssdd1@g...(惠惠大主教) d390
解題思路
355 2021-11-12 11:35
20893 m80126colin(許胖) d390
python 的同學
770 2020-03-17 03:24