# 【題解】Zerojudge d390: 00562 – Dividing coins

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d390
Virtual Judge: https://vjudge.net/problem/UVA-562
【解題想法】DP, 0-1 Knapsack

• 題目要求兩堆銅幣的「面值和」盡可能接近，等於求出最接近「所有銅幣價值總和」「一半」的最大值。
• dp[ half ] <= half <= sum / 2
• 答案 = ( sum – dp[ half ] ) – dp[ half ]
```#include <iostream>
#include <cstring>
using namespace std;
//一袋銅幣（裡面最多有 100 個，面值可能有 1 分錢到 500 分錢）
int t, m, total, half, dp[25005], coin[105];

int main(){
cin >> t;
while (t--){
cin >> m;
total = 0;
for (int i = 0; i < m; i++){
cin >> coin[i];
total += coin[i];
}
half = total / 2;
memset(dp, 0, sizeof(dp));
for (int i = 0; i < m; i++){
for (int j = half; j >= coin[i]; j--){
dp[j] = max(dp[j], dp[j-coin[i]] + coin[i]);
}
}
cout << total - dp[half] * 2 << "\n";
}
}
```

Python 程式碼 (credit: Amy Chou) – 會TLE

```T = int(input())
for Case in range(T):
m = int(input())
coin = list(map(int, input().split()))
Sum = sum(coin)
half = Sum // 2
dp = [0 for i in range(half+1)]

for i in range(m):
for j in range(half, coin[i]-1, -1):
if (dp[j - coin[i]] + coin[i] > dp[j]):
dp[j] = dp[j - coin[i]] + coin[i]

print(Sum - dp[half] * 2)
```