动态规划算法与贪心算法区别----找钱问题

http://blog.csdn.net/jarvischu/article/details/6056963
现只有面额为 11元、5元、1元的三种人民币。

      给定一个 数目为 money 的人民币，如何用这三种面额的人民币 找开它，且用的人民币张数最少

      如：给定 10元，我们可以有以下找法：

            2张  5元面额

            1张  5元面额  + 5 张  1元面额

            10张 1元面额

利用动态规划法可以找到最优解。

        利用贪心算法可以找到最优解（问题满足贪心选择性质时。该找钱问题在 11、5、1三种面额的情况下不满足该性质）

              或者找到近似 最优解（在本题设定的三种面额的情况下 便是如此）

        如果现在要找开 15元钱，则

        1. 根据动态规划法的解题思想，得到最优解为       3张  5元面额的 ，                                   总共 3张

        2. 根据贪心算法的解题思想，得到的近似最优解为 1张 11元面额的  加上  4张 1元面额的，     总共 5张

        从这就可以大略的看到 两个的区别
贪心算法核心就是：将总数每次减去可以减的最大数值，直到减完。
动态规划算法核心就是：将大问题化为小问题，从1到所要计算的数字所有的最优方法，从1推出2，2推出3，以此类推。。其中有一点是每一个都是类似的问题，但是并不独立，而是和之前计算结果相关。

/**********************************************************
 *问  题：有最小面额为 11 5 1的三种人民币，用最少的张数找钱
 *描  述：动态规划与贪心算法 解决问题 比较
 *作  者：JarvisChu
 **********************************************************/
#include<stdio.h>
#define N 4
#define VALUE1 11 //面额为 11元的人民币 （可以修改）
#define VALUE2 5 //面额为  5元的人民币 （可以修改）
#define VALUE3 1                 //面额为  1元的人民币 （不要修改，不然会有找不开的情况）
#define MAX_MONEY 1000 //能找开的钱的上限

/***************************动态规划法********************************
 *方法：
 *     int Num[MAX_MONEY]; //Num[i]保存要找开 i 元钱，需要的最小人民币张数
 *     int Num_Value[N][MAX_MONEY]; //Num_Value[i][j] 表示 要找 j元钱，需要面额 VALUEi 的人民币张数
 *
 * Num[i] = i; 0<= i <=4
 * Num[i] = min(Num[i-VALUE1]+1,Num[i-VALUE2]+1,Num[i-VALUE3]+1)
 */

//-------------------------求最小值---------------------------------
int min(int a,int b,int c){
    return a<b ? (a<c ? a:c):(b<c ? b:c);
}
//-------------------------求最优值---------------------------------
int DP_Money(int money,int Num[]){
                                             //获得要找开money元钱，需要的人民币总张数
    int i;
    for(i=0;i<=VALUE2;i++){                                 //0~4 全用 1元
        Num[i]=i;
    }
    for(i=VALUE2;i<=money;i++){                             //从5元开始 凑钱
        if(i-VALUE1 >= 0){                                 //如果比 11 元大，说明多了一种用11元面额人民币的可能
                                                         //从用 11元、5元、1元中 选择一个张数小的
            Num[i] = min(Num[i-VALUE1]+1,Num[i-VALUE2]+1,Num[i-VALUE3]+1);
        }
        else{                                         //从5元、1元中 选择一个张数小的
            Num[i] = (Num[i-VALUE2]+1) < (Num[i-VALUE3]+1) ? (Num[i-VALUE2]+1):(Num[i-VALUE3]+1);
//            Num[i] = min(Num[i-VALUE2]+2,Num[i-VALUE2]+1,Num[i-VALUE3]+1);
        }
    }
    return Num[money];
}
//-------------------------求最优解---------------------------------
void BestChoice(int money,int Num[],int Num_Value[N][MAX_MONEY]){
                                                         //要找 money 元钱，总人民币张数放在Num[money]中
                                                         //Num[1~3][money]分别保存三种面额的张数
    int i;
    for(i=0;i<VALUE2;i++){
        Num_Value[1][i] = 0;
        Num_Value[2][i] = 0;
        Num_Value[3][i] = i;
    }
    for(i=VALUE2;i<=money;i++){
        if((i>=VALUE1) && (Num[i] == (Num[i-VALUE1]+1))){ //i 是由 i-11+11 构成  即i元是由 i-11元 加上一张面额11元的人民币构成
            Num_Value[1][i] = Num_Value[1][i-VALUE1]+1; //多一张 11元面额人民币
            Num_Value[2][i] = Num_Value[2][i-VALUE1]; // 5元面额人民币 张数一样多
            Num_Value[3][i] = Num_Value[3][i-VALUE1]; // 1元面额人民币 张数一样多
        }
        else if(Num[i] == (Num[i-VALUE2]+1)){ //i 是由 i-5+5 构成
            Num_Value[1][i] = Num_Value[1][i-VALUE2]; //11元面额人民币 张数一样多
            Num_Value[2][i] = Num_Value[2][i-VALUE2]+1; //多一张 5元面额人民币
            Num_Value[3][i] = Num_Value[3][i-VALUE2]; // 1元面额人民币 张数一样多
        }
        else if(Num[i] == (Num[i-VALUE3]+1)){ //i 是由 i-1+1 构成
            Num_Value[1][i] = Num_Value[1][i-VALUE3]; //11元面额人民币 张数一样多
            Num_Value[2][i] = Num_Value[2][i-VALUE3]; // 5元面额人民币 张数一样多
            Num_Value[3][i] = Num_Value[3][i-VALUE3]+1; //多一张 1元面额人民币
        }
        else{
        }
    }
}

/***************************贪心算法********************************
 *方法：
 * Num_Value[i]表示 面额为VALUEi 的人民币用的张数
 * 能用大面额的人民币，就尽量用大面额
 */
int Greed(int money,int Num_Value[]){
   //要找开 money元人民币，Num_Value[1~3]保存 三种面额人民币的张数
    int total=0; //总张数，返回值也即是总张数。
    Num_Value[1] = 0;
    Num_Value[2] = 0;
    Num_Value[3] = 0;
    for(int i=money;i>=1;){
        if(i >= VALUE1){
            Num_Value[1]++;
            i -= VALUE1;
            total++;
        }
        else if(i >= VALUE2){
            Num_Value[2]++;
            i -= VALUE2;
            total++;
        }
        else if(i >= VALUE3){
            Num_Value[3]++;
            i -= VALUE3;
            total++;
        }
        else{
        }
    }
    return total;
}
void main(){
    //比较两个算法
    int i;
    int dp,grd; //分别保存动态规划法和贪心算法得到的人民币总张数
    int money; //要找的钱
    int Num[MAX_MONEY]; //Num[i]保存要找i花费的银币的数目
    int Num_Value[N][MAX_MONEY]; //Num_Value[i][j] 表示 要找 j 花费的 面值为 VALUEi 的硬币 的数目
    int Num_Value_Greed[N]; //Num_Value_Greed[i] 表示 面值为VALUEi 的人民币 数目
    money = 15; //可以为任意非负整型值（15 元是一个比较典型的可以区分两种算法的值）
    dp = DP_Money(money,Num); //动态规划法
    BestChoice(money,Num,Num_Value);
    grd = Greed(money,Num_Value_Greed); //贪心算法
    printf("要找的钱 为：%d\n",money);
    printf("  算法    张数  11元  5元  1元\n");
    printf("动态规划  %-4d  %-4d  %-3d  %-3d\n",dp,Num_Value[1][money],Num_Value[2][money],Num_Value[3][money]);
    printf("贪心算法  %-4d  %-4d  %-3d  %-3d\n",grd,Num_Value_Greed[1],Num_Value_Greed[2],Num_Value_Greed[3]);
}