d390. 00562 - Dividing coins
標籤 : DP 子集和問題
通過比率 : 715人/837人 ( 85% ) [非即時]
評分方式:
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 (碼畜) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
28058 goodsssdd1@g ... (惠惠大主教) d390
解題思路
901 2021-11-12 11:35
20893 m80126colin (許胖) d390
python 的同學
1186 2020-03-17 03:24