找零钱问题(dynamic programing)

找零钱问题(dynamic programing)

问题描述

现需要找钱123元，有1、2、5、10、20、50元的货币，用动态规划算法算出至少需要几张货币可以找开123元钱。 注：本题用贪心算法更简单，但是这里仅说明dp

解题思路

首先动态规划执行的过程需要用一张表(即二维数组)记录下来，我们创建一个7*124的二维数组num[7][124]，其中0行0列不用，第i行表示用第1 ~ i种货币找钱，第j列表示找j元钱。num[i][j]表示第1~i种货币找j元钱最少的货币数量，用从第1行开始填表，填到右下角时则得到最少的货币。

首先填第一行元素用1元钱找1、2、3…123元钱，填入的直接就是1、2、3…123。

填第2 ~ 6 行的时候，如果要找的钱小于当前最大的货币时，直接用之前的货币找 ，相当于现在第i种货币无法使用，即num[i][j] = num[i-1][j]。如果要找的钱大于当前使用最大的货币时，先用当前的货币找钱(当前货币最大，使用的越多，货币数量越少)，剩余的用之前的货币找 ，即num[i][j] = j/value[i] + num[i -1] [ j%value[i]]

(value[i]表示第i种货币的价值，即存放的1、2、5、10、20、50)

代码

#includeusing namespace std;void leastMoney(int value[],int price,int num[7][124]){ //货币必须时从1开始增大，否则可能有的钱找不开 for(int j=1; j<=123; j++) num[1][j] = j;//货币为 1 时 for(int i=2; i<=6; i++)//表示用前 i 种货币找钱 { for(int j=1; j<=123; j++)//j表示要找的钱 { if( j < value[i] ) //当要找的钱小于当前的货币时，直接用之前的货币找 num[i][j] = num[i-1][j]; else //当要找的钱大于当前的货币时，先用当前的货币找钱，剩余的用之前的货币找 { num[i][j] =num[i-1][j%value[i]]+j/value[i]; } } }}int main(){ int value[7] = {0,1,2,5,10,20,50}; int num[7][124] = {0}; leastMoney(value,123,num); for(int i=1;i<7;i++) { for(int j=1; j<124; j++) { if(j==123) cout<

运行结果

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。