无向图的动态规划——硬币问题

以你之姓@ 2022-05-08 12:36 235阅读 0赞

> 题目描述：  
> 硬币找零问题描述：现存在一堆面值为 V1、V2、V3 … 个单位的硬币  
> 问最多和最少需要多少个硬币才能找出总值为T个单位的零钱？  
> 输入：  
> 第一行为n，T，表示硬币个数，需要凑的面额，第二行有n个数，表示硬币的面额  
> 输出：  
> 一行，分别为最大最小的数目，用空格分开  
> 示例：  
> 输入 5 63  
> 1、2、5、21、25  
> 输出 63 3  
> 解题思路：  
> 运用动态规划，将 Max【T】和Min【T】用来存储总面额为T时所需要的最多和最少  
> 的硬币，Max【T】=max\{Max【T-Vi】+1，Max【T】\}，Min【T】=min\{Min【T-vi】+1，  
> Min【T】\}，将min【Vi】初始化为1，将max【vi】初始化为1
> 
> \--------------------- 作者：braveryCHR 来源：CSDN 原文：https://blog.csdn.net/bravery\_again/article/details/72458067?utm\_source=copy

## 贪心解决： ##

关于最少硬币的数目，可以用贪心算法——每次选尽可能大的硬币，直至满足条件。

证明：见参考文章

代码：

#include<iostream>
    #include<vector>
    #include<stack>
    #include<algorithm>
    using namespace std;
    
    const int maxnum=100;
    
    int find_less(vector<int> &type,stack<int> &money,int s)
    {
    	int sum=0,bakesum;
    	int len=type.size();
    	int i;
    	for(i=len-1;i>=0;i--)
    	{
    		while(sum<s)
    		{
    			sum+=type[i];
    			money.push(type[i]);
    			if(sum==s)
    				return 1;
    		}
    		sum-=type[i];
    		money.pop();
    	}
    	return 0;
    }
    
    int main()
    {
    	vector<int> type;//存钱的种类 
    	stack<int> money;//存已经放入的钱
    	int i,n,s;//用于记数，钱的种类数，总金额
    	int tmp;
    	//输入 
    	cin>>n; 
    	for(i=0;i<n;i++)
    	{
    		cin>>tmp;
    		type.push_back(tmp);
    	}
    	cin>>s;
    	sort(type.begin(),type.end());//将面额从小到大排序
    	
    	if(find_less(type,money,s))
    	{
    		while(!money.empty())
    		{
    			tmp=money.top();
    			cout<<tmp<<" ";
    			money.pop();
    		}
    	}
    	else
    		cout<<"no way";
    	
    	return 0;
    }

### 动态规划——图： ###

开始的时候，怎么也想不出来咋可以用图来解决。后来想通了（如下图所示）。

![70][]

用递归的方式：

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<climits>
    using namespace std;
    
    const int INF=10000;
    const int maxmoney=100;
    int Max[maxmoney];
    int Min[maxmoney];
    vector<int> type;
    int n;
    
    int minnum(int s)
    {
        if(Min[s]!=-1)
            return Min[s];
        Min[s]=INF;
        for(int i=0; i<n; i++)
            if(s>=type[i])
                Min[s]=min(Min[s],minnum(s-type[i])+1);
        return Min[s];
    }
    
    int maxnum(int s)
    {
        if(Max[s]!=-1)
            return Min[s];
        Max[s]=-INF;
        for(int i=0; i<n; i++)
            if(s>=type[i])
                Max[s]=max(Max[s],maxnum(s-type[i])+1);
        return Max[s];
    }
    
    int main()
    {
        
        int i,m;
        cin>>n>>m;//n表示零钱的种类，m表示总金额
        int tmp;
        for(i=0;i<n;i++)
        {
            cin>>tmp;
            type.push_back(tmp);
        }
        sort(type.begin(),type.end());
        
        Max[0]=0;Min[0]=0;
        for(i=1;i<=m;i++)
        {
            Max[i]=-1;
            Min[i]=-1;
        }
        
        cout<<minnum(m)<<" "<<maxnum(m);
    }

用递推的方式：

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<climits>
    using namespace std;
    
    const int INF=10000;
    const int maxmoney=100;
    int Max[maxmoney];
    int Min[maxmoney];
    
    int main()
    {
    	
    	int i,n,m;
    	vector<int> type;
    	cin>>n>>m;//n表示零钱的种类，m表示总金额 
    	int tmp;
    	for(i=0;i<n;i++)
    	{
    		cin>>tmp;
    		type.push_back(tmp);
    	}
    	sort(type.begin(),type.end());
    	
    	Max[0]=0;Min[0]=0;
    	for (int i=1;i<=m;++i)
    	{
            Min[i]=INF;  //初始化为最大 
            Max[i]=-INF; //初始化为最小 
        }
    	
    	
    	int t;
    	for(t=1;t<=m;t++)
    	{
    		for(i=0;i<n;i++)
    			if(t>=type[i])
    			{
    				Max[t]=max(Max[t],Max[t-type[i]]+1);
    				Min[t]=min(Min[t],Min[t-type[i]]+1);
    			}
    	}
    	
    	cout<<Max[m]<<" "<<Min[m]<<endl;
    	
    	return 0;
    }

参考文章：

[某种 找换硬币问题的贪心算法的正确性][Link 1]

[证明][Link 1][刘如佳书p164--硬币问题][p164--]

[70]: /images/20220508/e3367ba2b8c94061aa605cf1f571fc2a.png
[Link 1]: https://www.cnblogs.com/hapjin/p/5575112.html
[p164--]: https://blog.csdn.net/sunbaofeng2/article/details/7974656