【数据结构】贪心算法（人民币、分糖果）

分手后的思念是犯贱 2022-05-16 00:39 301阅读 0赞

## 【0】目录 ##

**一、贪心算法存于生活中**  
**1.1人民币支付问题**  
**1.1.1算法思想**  
**1.1.2程序实现**  
**1.1.3程序结果**  
**1、举个实例**  
**二、分糖果 leetcode455**  
**2.1举个实例**  
**2.2贪心规律**  
**2.3算法思路**  
**2.4程序实现**  
**2.5程序结果**

## 一、贪心算法存于生活中 ##

**1、人民币支付问题**  
现在去超市买东西，结账时，要求支付一定金额的现金，那么，按照生活常识，我们肯定会选择尽可能少的拿出钱的张数去满足支付金额，比如说：应付**628**元，这时候，我的钱包里有**足够多**的以下面额的钱：100，50，20，10，5，2，1，那么，我肯定会拿出**6张100块**的，**1张20**的，**1张5块**的，**1张2块**的，最后再拿出**1张1块**的，`6*100+20+5+2+1 = 628`；那么我用10张就可以愉快的完成支付了，正常情况下，**绝对不会拿628张1块**的去支付或者其它。  
那么，将这种思想体现在编程上，就是我们所称的**贪心算法**。  
**贪心算法：遵循某种规律，不断贪心的选取当前最优策略的算法设计方法。**  
就上面的例子，体现在编程中如下：

## 一、人民币 ##

**1、算法思想**  
（1）面值为100，50，20，10，5，2，1面值都是比自己小的面值的两倍或者以上；  
（2）当使用一张较大面额时，若用较小面额钞票替换，则需要两张或者更多张钞票。  
**2、程序实现**

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    class solution
    {
    public:
    	int HowManycash(vector<int> RMB,const int num,int waitTOpay)
    	{
    		int count = 0;//记录总共需要多少张钱
    		for(int  i =0 ;i<num ;++i)
    		{
    			int use = waitTOpay/RMB[i];//记录每一种面额需要多少张
    			count += use;
    			waitTOpay = waitTOpay - RMB[i]*use;
    			printf("需要面额为 %d 的 %d 张:,",RMB[i],use);
    			printf("剩下需要支付 RMB %d \n",waitTOpay);
    		}
    	
    		printf("总共需要%d张RMB\n",count);
    		return count;
    
    	}
    
    };
    int main()
    {
    	solution solve;
    	std::vector<int> RMB;
    	RMB.push_back(100);
    	RMB.push_back(50);
    	RMB.push_back(20);
    	RMB.push_back(10);
    	RMB.push_back(5);
    	RMB.push_back(2);
    	RMB.push_back(1);
    
    	int num = RMB.size();
    	int waitTOpay = 628;
    	solve.HowManycash(RMB,num,waitTOpay);
    	return 0;
    }

**3、程序结果**\*\*  
![70][]

## 二、分糖果 leetcode455\#\# ##

已知有一些孩子和一些糖果，每个孩子都有需求因子g，每个糖果有大小s；如果某个糖果的大小s>=某个孩子的需求因子时，代表该糖果可以满足该孩子，使用这些糖果，最多可以满足多少孩子？（注意：某个孩子最多只能被一块糖果满足）  
**1、举个实例**  
孩子的需求因子为g = \[5， 10， 2，9，15，9\]；糖果的大小数组为：s = \[6，1，20，3，8\]，那么，这种情况下，最多可以，满足3个孩子。

**2、贪心规律**  
（1）某个糖果不能满足某个孩子，那么，该糖果一定不能满足更大需求因子的孩子。  
（2）某个孩子可以用更小的糖果满足，则没必要用更大的糖果，留着更大的糖果去满足需求因子更大的孩子。（**贪心！！**）  
（3）孩子的需求因子更小则其更容易被满足，故优先从需求因子小的孩子开始，因为用一个糖果满足一个较大需求因子的孩子或满足较小需求因子的孩子效果一样。（最终总量不变）（**贪心！！**）

**3、算法思路**  
（1）对需求因子数组g和糖果大小数组s进行从小到大排序；  
（2）按照从小到大的顺序使用各糖果，尝试是否可以满足某个孩子，每个糖果只尝试一次；若成功，则换下一个糖果尝试；直到发现没有孩子或者没有糖果，循环结束。  
**4、程序实现**

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    void print(std::vector<int> v)//打印函数
    	{
    		int length = v.size();
    		for(int i = 0; i<length ; ++i)
    		{
    			printf("%d ",v[i]);
    		}
    	printf("\n");
    	}
    	
    class solution
    {
    public:
    	int candygivechildren(std::vector<int> g,std::vector<int> &s)//分配函数
    	{
    		std::sort(g.begin(),g.end());
    		printf("孩子需求排序后数组：");
    		print(g);
    		std::sort(s.begin(),s.end());
    		printf("糖果排序后数组：");
    		print(s);
    		int child = 0;
    		int cookie = 0;
    			while(child < g.size() && cookie <s.size())
    			{
    				if(g[child] < s[cookie])
    				{
    					++child;
    				}
    				++cookie;
    			}
    			return child;
    	}
    };
    
    int main()
    {
    	solution solve;
    	std::vector<int> g;
    	std::vector<int> s;
    	g.push_back(5);
    	g.push_back(10);
    	g.push_back(2);
    	g.push_back(9);
    	g.push_back(15);
    	g.push_back(9);
    	printf("孩子需求原数组：");
    	print(g);	
    	s.push_back(6);
    	s.push_back(1);
    	s.push_back(20);
    	s.push_back(3);
    	s.push_back(8);
    	printf("糖果原数组：");
        print(s);
    	printf("\n能有 %d 个孩子的糖果愿望能满足",solve.candygivechildren(g,s));
    	return 0;
    }

**5、程序结果**  
![70 1][]

[70]: /images/20220516/30277d1a94934d4eaec65393a8481bbe.png
[70 1]: /images/20220516/f491132039794645ac81aa1bf6663c4e.png