Algoogle

Algorithm for Programming Contest

PKU 3260 The Fewest Coins

Category: PKU Tag: dp

The Fewest Coins

問題概要


コインの価値と個数と, 目的の金額が与えられる.
目的の金額を支払うとき, 自分が使うコインと店員が渡すお釣りのコインの数の最小はいくらか.
ただし店員はコインを無限に持っていて, お釣りのコインは最適になるように渡す.
すべての場合で支払い, もしくはお釣りがだせない場合は-1をだす.

解法


それぞれの金額について
自分が支払うときの最適を個数制約付きナップザックで
店員が渡すときの最適を制約なしナップザックで解く.
コインの価値がナップザックの重さ, 枚数がナップザックの価値にあたる.
それらから, 支払いの枚数+お釣りの枚数が最小になるものをさがす.

個数制約付きナップザックはスライド最小値でもできるが計算量がそこまでシビアではなかったのでビットを用いたdpで01ナップザックとして解いた.

コード


(3260.cpp) download
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
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>

using namespace std;

typedef pair<int,int> pii;

const int M = 20000;
int N, T, V[128], C[128];
int change[20010], pay[20010];
pii deq[20010];

int main(){
    scanf("%d%d", &N, &T);
    for(int i = 0; i < N; i++)
        scanf("%d", V+i);
    for(int i = 0; i < N; i++)
        scanf("%d", C+i);

    for(int i = 0; i < N; i++)
        for(int j = V[i]; j <= M; j++)
            if(change[j-V[i]] or j == V[i])
                change[j] = change[j] > 0? min(change[j], change[j-V[i]]+1): change[j-V[i]]+1;

    for(int i = 0; i < N; i++){
        int num = C[i];
        for(int j = 1; num > 0; j<<=1){
            int mul = min(num, j);
            num -= mul;
            for(int k = M; k - mul*V[i] >= 0; k--)
                if(k-mul*V[i] == 0 or pay[k-mul*V[i]] > 0)
                    pay[k] = pay[k] > 0? min(pay[k], pay[k-mul*V[i]]+mul): pay[k-mul*V[i]]+mul;
        }
    }
    int ans = int(1e9);
    for(int i = T; i <= M; i++)
        if(pay[i] and (change[i-T] or i == T))
            ans = min(ans, pay[i] + change[i-T]);
    if(ans == int(1e9)) printf("-1\n");
    else printf("%d\n", ans);
    return 0;
}

Comments