动态规划求解‘货币兑付问题’

小灰灰 2022-05-22 11:50 188阅读 0赞

### 问题描述： ###

在面值为(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 ，则要考虑支付后是否可以使硬币的枚数减少（本题不考虑）  
![这里写图片描述][70]

### 实验题目 ###

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

#include<iostream>
    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<num2)
    			return num1;
    		else
    			return num2;
    	}
    	//有一个没有解，或都没有解
    	else
    	{
    		if(num2==-1)
    			return num1;
    		return num2;
    	}
    }
    
    
    int main()
    {
    	//初始化硬币的面值
    	int money[M+1]={0,1,2,5,7,9};
    	//来保存标识该硬币选取了几个
    	int count[M+1]={0};
    
    	int n;  //用来接收需要支付的金额
    	cout<<"请输入需要支付的金额：";
    	cin>>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、动态规划求解‘找硬币个数’的表格："<<endl;
    	//因为第一行是-1  所以单独输出，否则格式对不齐，注意还有空格，空格删去就对不齐了。
    	cout<<"\t ";
    	for(j=0;j<=n;j++)
    		cout<<" "<<a[0][j];
    	cout<<endl;
    	for(i=1;i<=M;i++)
    	{
    		cout<<"\t";
    		for (j=0;j<=n;j++)
    		{
    			cout<<"  "<<a[i][j];
    		}
    		cout<<endl;
    	}
    	cout<<"\n2、选择的硬币为："<<endl;
    	cout<<"\t\t面值\t个数"<<endl;
    	for(i=1;i<=M;i++)
    	{
    		cout<<"\t硬币"<<i<<"\t"<<money[i]<<"\t"<<count[i]<<endl;
    	}
    
    
    
    	//4、输出结果
    	int sum=0;
    	cout<<"\n3、最少的硬币数为："<<a[M][n]<<"个，计算公式：";
    	for(i=1;i<=M;i++)
    	{
    		if(count[i]>0)
    		{
    			//判断sum是否等于输入的金额，如果等于了，那么就不用输出‘+’号了
    			sum+=money[i]*count[i];
    			if(sum!=n)
    				cout<<money[i]<<"*"<<count[i]<<"+";
    			else
    				cout<<money[i]<<"*"<<count[i];
    		}
    	}
    	cout<<"="<<sum<<"\n"<<endl;
    	return 0;
    }

--------------------

### 算法分析： ###

这个问题的思想和0/1背包问题一样，利用二位数组将子问题的解保存下来，然后根据当前的状态来求解当前的解。  
  核心：  
    1、填写二位数组，判断当前位置需支付的金额是否大于硬币的价值，大于就使用该硬币支付，并判断子问题与新解哪个更优，取优值；否则就是上一行该列的值，即子问题的解。  
    2、求完二位数组后，要知道是使用那些硬币来支付的，这里与背包问题稍微有些不同，背包问题只用知道某件物品装或没装，而硬币问题还需要知道该枚硬币使用了几枚。所以我们定义整形的一维数组来标识该物品装入的数量即可，让它的初值为0，表示使用0枚，这样循环下来，使用过的硬币就不会是0，对应输出它的值就可以知道某枚硬币使用了几个。

--------------------

### 实验结果： ###

![这里写图片描述][70 1]  
![这里写图片描述][70 2]

### 总结： ###

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

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

> 答案：  
> 第一个人：97，0，1，2，0  
> 第二个人：98，0，1，1  
> 第三个人：100，0，0

[70]: /images/20220522/71a902e681f844b4a680dc91bfe5bf3b.png
[70 1]: /images/20220522/ea6f26423a174da4a4184a0e57025682.png
[70 2]: /images/20220522/c86aba15c99f4f73adf1523f65c9d895.png