Problem Solving►UVa

UVa 562 - Dividing coins

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

用給的錢幣分成兩堆，使的相差盡可能的少。

Solution

將錢數相加後除以二，用 DP 求出 dp[half] 時可湊出的最大金額。另一半是剩下的錢，相減即為答案。

有遇到類似問題，想試著直接用 greedy 解，從大取到小或小取到大，每次將數字往小堆的丟。
但很明顯會有問題，提供幾個例子: 

5
7 8 10 100 105
4    
2 3 100 101

輸出皆為 0 。

Code

UVa 562UVa 562 - Dividing coins
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
#define MAX(a,b) ((a)>(b)?(a):(b))

int main()
{
    int Case, num[100], dp[50001];
    scanf("%d", &Case);
    while (Case--)
    {
        int n, i, k, sum = 0;
        scanf("%d", &n);
        for (i = 0; i < n; i++)
        {
            scanf("%d", &num[i]);
            sum += num[i];
        }

        int half = sum >> 1;
        for (i = 0; i <= half; i++)
            dp[i] = 0;

        //從一半開始做 dp ，dp[k] 表此時可以湊到的最多錢數 小於等於 k
        for (i = 0; i < n; i++)
            for (k = half; k >= num[i]; k--)//不重複使用，top-down
                dp[k] = MAX(dp[k], dp[k - num[i]] + num[i]);

        printf("%d\n", (sum - dp[half]) - dp[half]);//大於等於一半的 = sum - dp[half]，在減掉 dp[half] 即是相差的了
    }

    return 0;
}