Chpt5-贪心技术-算法5.1--付款问题(Pay)

//最近发生了一些事情，让我觉得难过，所以，算法的复习停滞了下来。。。

//不能说清楚这是借口还是理由，总之，心绪不宁的状态还在继续 -_-b

 

这是个很简单地说明贪心策略的例子，已知钞票面额，由用户输入要付款数，输出如何找零的话使用的钞票张数最少。（避免弄个硬币砸人的事情发生...）

 

在这里，贪心算法总是能得到最优解的，这个和钞票面额的划分有关。

 

#include
#include

#define MAX_PAY 10000
#define MONEY_TYPE 12

int money[MONEY_TYPE] = {5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1};

/*Show usage*/
void usage(char * prog)
{
        printf("%s Usage:\n", prog);
        printf("%s \n", prog);
}

/*Algorithm*/
void pay(int * money, int to_pay)
{
        int i, re, topay[MONEY_TYPE];

        for(i = 0; i < MONEY_TYPE; i ++)
                topay[i] = 0;

        re = to_pay;
        i = 0;
        while(re > 0)
        {
                if(money[i] <= re)
                {
                        re -= money[i];
                        topay[i] ++;
                }
                else
                        i ++;
        }

        for(i = 0; i < MONEY_TYPE; i ++)
        {
                if(topay[i] != 0)
                {
                        if(money[i] >= 100)
                                printf("%4d CNY: %d\n", money[i]/100, topay[i]);
                        else
                        {
                                printf("%.2f CNY: %d\n", (float)(money[i])/100, topay[i]);
                        }
                }
        }
}

int main(int argc, char * argv[])
{
        int shouldpay = 0;
        if(argc != 2)
        {
                usage(argv[0]);
                exit(127);
        }

        shouldpay = atoi(argv[1]);

        if(!shouldpay || shouldpay > MAX_PAY)
        {
                usage(argv[0]);
                exit(128);
        }

        pay(money, shouldpay);

        return 1;
}