【題解】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)
分享本文 Share with friends