【題目敘述】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)