↓快轉到主要內容
  1. Uva/

[UVa] 562 Dividing coins

·
UVa dynamic programming
目錄

題目敘述
#

562 Dividing coins

給定 n 個錢幣，求出將 n 個錢幣分成兩堆，且兩堆錢幣面額總和最小的差值。

解題思路
#

這題使用暴力法的話複雜度為 2^100，明顯不是可行的方案，因此需要考慮其他方法。

因為題目要求兩者金額的差異要最小，可以換一個角度來想，我們應該要找出一個分配方法，來讓一方的金額最接近總和的二分之一。

求出最接近但不超過總金額的二分之一的最大值，可以想到動態規劃中的 knapsack。總金額的二分之一為背包的負重。

程式碼
#

#include <bits/stdc++.h>
using namespace std;

int n, m;
int coins[105];
int dp[25005]; // max sum is 50000, just need half of it

void slove() {
    // init
    memset(dp, 0, sizeof(dp));

    cin >> m;
    int sum = 0;
    for (int i = 0; i < m; ++i) {
        cin >> coins[i];
        sum += coins[i];
    }
 
    dp[0] = 1;
    for (int i = 0; i < m; ++i) {
        for (int j = sum / 2; j >= coins[i]; --j) {
            dp[j] = max(dp[j], dp[j-coins[i]]);
        }
    }

    for (int i = sum / 2; i >= 0; --i) {
        if (dp[i]) {
            cout << sum - 2 * i << endl;
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    while (n--) {
        slove();
    }

    return 0;
}