d390. 00562 - Dividing coins
Tags : DP 子集和問題
Accepted rate : 772人/906人 ( 85% ) [非即時]
評分方式:
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 (碼畜) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
43509 chiuliyou@gm ... (邱立宇) d390
動態規劃五步法
126 2024-10-21 01:00
41084 seancai78@gm ... (風月春秋) d390
背包問題轉換
203 2024-07-02 13:33
28058 goodsssdd1@g ... (惠惠大助教) d390
解題思路
1139 2021-11-12 11:35
20893 m80126colin (許胖) d390
python 的同學
1414 2020-03-17 03:24