d390. 00562 - Dividing coins
標籤 : DP 子集和問題
通過比率 : 755人/883人 ( 86% ) [非即時]
評分方式:
Tolerant

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

內容

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

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

輸入說明

輸入的第一列有一個整數

代表以下有幾組測試資料

每組測試資料 2 列

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

代表袋中銅幣的數目

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

代表袋中各銅幣的面值

輸出說明

對每一組測試資料

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

範例輸入 #1
2
3
2 3 5
4
1 2 4 6
範例輸出 #1
0
1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
提示 :

* 中文翻譯:Lucky 貓 

DP (背包問題(Knapsack Problem))

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

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
43509 chiuliyou@gm ... (邱立宇) d390
動態規劃五步法
46 2024-10-21 01:00
41084 seancai78@gm ... (風月春秋) d390
背包問題轉換
142 2024-07-02 13:33
28058 goodsssdd1@g ... (惠惠大助教) d390
解題思路
1082 2021-11-12 11:35
20893 m80126colin (許胖) d390
python 的同學
1361 2020-03-17 03:24