本文共 470 字，大约阅读时间需要 1 分钟。

将一个较大的钱，不超过1000的人民币，兑换成数量不限的100、50、10、5、2、1的组合，请问共有多少种组合呢？ 

解法：01背包中的完全背包问题（即每个物品的数量无限制） dp[i][j]：表示大小为j的价值用最大为money[i]可表示的种类数

#define NUM 7 

int money[NUM] = {1, 2, 5, 10, 20, 50, 100};   // 动态规划解法(完全背包)    

int NumOfCoins(int value)   {   

    int dp[7][1010];   

    for(int i = 0; i <= value; ++i)         

dp[0][i] = 1;      

    for(int i = 1; i < NUM; ++i){ 

        for(int j = 0; j <= value; ++j){ 

            if(j >= money[i])   

                dp[i][j] = dp[i][j-money[i]] + dp[i-1][j];               

else   

                dp[i][j] = dp[i-1][j];           

}       

}   

    return dp[6][value]; 

}

转载地址：http://uvirj.baihongyu.com/