Problem Solving►UVa

UVa 11517 - Exact Change

Contents

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

Problem

題目網址
中文網址

Solution

方法一：

dp[i]: 所能湊到的 >= i 的錢中最接近的。
dp[i] = -1: 無法湊到 >= i

amount[i]: 要湊到 >= i 的錢所使用的錢幣數

1
2
3
4
for (int k = 0; k < n; ++k)
    for (int i = price; i; --i)
        用目前的錢幣去湊 i ，看可不可以湊到越接近 i 的。
        相等時用錢幣數去比較。

方法二：(較慢)

dp[i]: 能不能湊到 i

amount[i]: 湊到 i 的錢幣數

直接從一個較大的數字(P)往回做，去看能不能湊得目標金錢： 

1
2
3
for (int k = 0; k < n; ++k)
    for (int i = P-1; i>=coin[k]; --i)
        ...

輸出答案時要找最接近的所以從小的開始找。

Code

(1)

UVa 11517
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <cstring>
#define N 100

int main()
{
    //freopen("test.out", "w", stdout);
    int T, coin[N];
    int dp[10001], amount[10001];

    scanf("%d", &T);
    while (T--)
    {
        memset(dp, -1, sizeof dp);
        memset(amount, 0, sizeof amount);
        dp[0] = 0;
        int n, price;

        scanf("%d%d", &price, &n);

        for (int i = 0; i < n; ++i)
            scanf("%d", &coin[i]);

        for (int k = 0; k < n; ++k)
        {
            for (int i = price; i; --i)
            {
                int idx = i - coin[k];
                if (idx >= 0)
                {
                    if (dp[idx] != -1) //有辦法湊到 i - coin[k]
                    {
                        int now = dp[idx] + coin[k]; //現在所湊到 >= i 的錢
                        int use = amount[idx] + 1;
                        if (now < dp[i] || dp[i] == -1) //取用最接近 i 的或是 i 還沒被湊出來
                        {
                            dp[i] = now;
                            amount[i] = use;
                        }
                        else if (now == dp[i] && amount[i] > use) //採用錢幣數較少的
                            amount[i] = use;
                    }
                }
                else if (dp[i] == -1 || dp[i] >= coin[k])//當前幣值大於 i
                {
                    dp[i] = coin[k];
                    amount[i] = 1;
                }
            }
        }

        printf("%d %d\n", dp[price], amount[price]);
    }

    return 0;
}

(2)

UVa 11517
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <cstring>
#define N 100
#define P 10001

int main()
{
    //freopen("test.out", "w", stdout);
    int T, coin[N];
    bool dp[P];
    int amount[P]= {};

    scanf("%d", &T);
    while (T--)
    {
        memset(dp, false, sizeof dp);

        dp[0] = true;
        int n, price;

        scanf("%d%d", &price, &n);

        for (int i = 0; i < n; ++i)
            scanf("%d", &coin[i]);

        for(int i=1; i<P; ++i)
            amount[i]=1e9;

        for (int k = 0; k < n; ++k)
            for (int i = P-1; i>=coin[k]; --i)
            {
                if(dp[i-coin[k]])
                {
                    dp[i] = true;
                    if(amount[i]>amount[i-coin[k]]+1)
                        amount[i] = amount[i-coin[k]]+1;
                }
            }

        for(int i=price; i<P; ++i)
        {
            if(dp[i])
            {
                printf("%d %d\n", i, amount[i]);
                break;
            }
        }
    }

    return 0;
}