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

问题描述：

  在面值为(v1, v2, …, vn)n种货币中，需要支付y值的货款，应如何支付才能使货币支付的张数最少。设计动态规划算法求解该问题

求解思路

  货币兑换问题可以看作是决策一个序列(v1, v2, …, vn)，对任一变量vi的决策是决定ni=x还是ni=0。在对vi-1决策后，已确定了(v1, …, vi-1)，在决策vi时，问题处于下列两种状态之一：

  （1）硬币面值vi超过要支付的面额pi，则ni=0，

  （2）硬币面值vi可以支付的要支付的面额pi ，则要考虑支付后是否可以使硬币的枚数减少（本题不考虑）

实验题目

  根据分析，完成货币兑付问题的代码，其中货币的个数为5，面值为1,2,5,7,9，需要支付的金额由用户输入。

#include
   
    using namespace std;#define M 5    //货币的种类数目#define N 1000  //最大的支付金额//定义存放动态规划子问题解的表格，M+1行N+1列   //每行每列都要多一个，因为要存放无解和无需支付的情况int a[M+1][N+1];    //取它们的最小值，谁有解取谁，如果都没有解，那么都是-1 ，返回谁都可以int min(int num1,int num2){	//都有解，选小的	if(num1!=-1 && num2!=-1)	{		if(num1
    
     >n;		int i,j;	//初始化表格	for(i=0;i<=M;i++)		a[i][0]=0;	for(j=1;j<=n;j++)		a[0][j]=-1;	//1、开始求解，填写表格	for(i=1;i<=M;i++)   //从下标都为1  开始	{		for(j=1;j<=n;j++)		{			//1、判断支付金额是否大于等于当前硬币的面值，如果大于等于那么可以支付，否则为子问题的解			//2、如果可以支付，判断子问题的解  和  使用该面值后的   硬币数  谁少取谁			if(j>=money[i])				a[i][j]=min(a[i][j-money[i]]+1,a[i-1][j]);			else				a[i][j]=a[i-1][j];		}	}	//2、求选择硬币的个数	j=n;	for(i=M;i>0;)	{		if(a[i][j]!=a[i-1][j])		{			count[i]++;			j-=money[i];		}		else			i--;	}		//3、输出二位表格	cout<<"\n1、动态规划求解‘找硬币个数’的表格："<
     
      0)		{			//判断sum是否等于输入的金额，如果等于了，那么就不用输出‘+’号了			sum+=money[i]*count[i];			if(sum!=n)				cout<
      
       <<"*"<
       
        <<"+";			else				cout<
        
         <<"*"<
        
       
      
     
    
   

算法分析：

  这个问题的思想和0/1背包问题一样，利用二位数组将子问题的解保存下来，然后根据当前的状态来求解当前的解。

实验结果：

总结：

  动态规划法，让人觉得这是个‘聪明的算法’，让我感觉到了把人的思想写成了代码，因为它每次都是根据当前的状态来决定下一步该做什么决策。最经典的问题是“海盗分钻石”问题。

  五个海盗抢了一百颗钻石，每颗都价值连城。五个海盗都很贪婪，他们都希望自己能分得最多的钻石，但同时又都很明智。于是他们按照抽签的方法排出一个次序。首先由抽到一号签的海盗说出一套分钻石的方案，如果5个人中有50％（以上）的人同意，那么便依照这个方案执行，否则的话，这个提出方案的人将被扔到海里喂鱼，接下来再由抽到二号签的海盗继续说出一套方案，然后依次类推到第五个。记住，五个海盗都很聪明哦！

答案：

第一个人：97，0，1，2，0

第二个人：98，0，1，1

第三个人：100，0，0