找零钱问题(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]]

代码

#include<iostream>

using 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<<num[i][j]<<endl;
      else cout<<num[i][j]<<" ";
    }
  }
  cout<<"最少的货币数量为:"<<num[6][123]<<endl;
  return 0; 
}      

运行结果