ACM: 166 – Making Change

換零錢的問題，要使用有限量的錢幣去支付一個商品，要找出支付和找錢(假設商家錢幣為無限量)所使用的總錢幣數量為最小。我的做法是，先找出在每一個金額，商家找錢使用的最少錢幣數量。然後根據買家的錢幣組合，找出所有可以支付的金額所使用的最少錢幣數量。最後找出支付+找錢總使用最少的錢幣數量。

在計算支付的部分，似乎怪怪的，應該有更有效率的做法，但是還想不到怎麼改，繼續研究。

CODE

#include <iostream>

#include <climits>

using namespace std;

enum { COINS = 6, MAX_CHANGE = 10000 };

int main(){

    const int coin[] = {1, 2, 4, 10, 20, 40};

    int p, q, //price

        w[COINS], //wallet

        change[MAX_CHANGE+1]; //change

    int i, j, k, m, sum;

    change[0] = 0;

    for(i=1; i<=MAX_CHANGE; ++i)

        change[i] = INT_MAX;

    for(i=0; i<COINS; ++i)

        for(j=coin[i]; j<=MAX_CHANGE; j++)

            change[j] = min(change[j-coin[i]]+1, change[j]);

    while(1){

        sum = 0;

        for(i=0; i<COINS; ++i){

            scanf("%d", &w[i]);

            sum += w[i] * coin[i];

        }

        if( sum == 0 ) break;

        scanf("%d.%d", &p, &q);

        p = (p*100+q)/5;

        int* pay = (int*)malloc((sum+1) * sizeof(int));

        int* use = (int*)malloc((sum+1) * sizeof(int));

        if( pay == NULL || use == NULL ) exit(1);

        pay[0] = 0;

        for(i=1; i<=sum; ++i)

            pay[i] = INT_MAX;

        for(i=0; i<COINS; ++i){

            for(j=1; j<=coin[i]; ++j){

                m = w[i];

                for(k=j; k<=sum; k+=coin[i]){

                    if( pay[k] != INT_MAX ){

                        m = w[i];

                    }

                    else if( k < coin[i] ){ break; }

                    else if( m > 0 ){

                        pay[k] = pay[k-coin[i]] + 1;

                        --m;

                    }

                }//k

            }//j

            memset(use, 0, (sum+1) * sizeof(int));

            for(j=coin[i]; (j<=sum) && (use[j-coin[i]] < w[i]) ; ++j){

                if( (pay[j-coin[i]] != INT_MAX) && (pay[j-coin[i]]+1 <= pay[j]) ){

                    pay[j] = pay[j-coin[i]] + 1;

                    use[j] = use[j-coin[i]] + 1;

                }

            }

        }//i: coins

        int total = INT_MAX;

        for(i=p; i<=sum; ++i)

            if( pay[i] != INT_MAX )

                total = min(pay[i]+change[i-p], total);

        printf("%3d\n", total);

        free(pay);

        free(use);

    }

    return 0;

}