433-贪心算法编程实战

向右看齐 2022-09-05 06:10 175阅读 0赞

## 贪心算法思想 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
**贪心算法：符合每一步的最优解，但是不一定是原问题的最优解**

## 硬币问题 ##

**1,3,5分的硬币，现在给定一个价值c：11，问组成价值c需要的最少的硬币的数量？？？**  
**贪心算法**，就是一直优先选大的面值的硬币。  
刚开始一直选5分硬币，选不了5分的硬币了，就选3分的，3分的硬币也选不了了，就选1分的硬币。

#include <iostream>
    #include <algorithm>//泛型算法的头文件
    using namespace std;
    
    int main()
    {
        
    	int arr[] = {
         1,3,5 };
    	int length = sizeof(arr) / sizeof(arr[0]);
    	int c = 11;
    
    	sort(arr, arr + length, [](int a, int b)->bool {
        return a > b; });//降序排序 
    
    	int idx = 0;// 5 3 1
    	int cnt = 0;//记录硬币的个数
    	while (c > 0) 
    	{
        
    		if (c >= arr[idx])
    		{
        
    			c -= arr[idx];
    			cnt++;//硬币数加1
    		}
    		else 
    		{
        
    			idx++;//数组下标往后走
    		}
    	}
    
    	cout << cnt << endl;
    
    	return 0;
    }

**运行截图如下**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]

## 部分背包问题 ##

**部分背包问题**  
有n个物体，第i个物体的重量为wi，价值为vi。在总重量不超过C的情况下让总价值尽量高。  
**也就是说，每一个物体都可以只取走一部分，价值和重量按比例计算。求最大总价值。**  
**也就是说，贪心算法可以一定要把c占满，优先把价值高的往里放。**

**贪心算法 -解决01背包 - 不一定得到最优解，因为在0-1背包，物品只存在放与不放，不能只放一个物品的其中的一部分，所以最后不一定把背包的容量占满**

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    //描述物品的类
    struct Product
    {
        
    	double getPrice()const//获取性价比 
    	{
        
    		return v * 1.0 / w;
    	}
    	bool operator>(const Product& p) const//重载大于> 
    	{
        
    		return getPrice() > p.getPrice();
    	}
    	int id;//物品的id
    	int w;//物品的重量
    	int v;//物品的价值
    };
    
    int main()
    {
        
    	int w[] = {
         8,6,4,2,5 };
    	int v[] = {
         6,4,7,8,6 };
    	const int n = sizeof(w) / sizeof(w[0]);//物品的个数
    	int c = 12;
    	int x[n] = {
         0 };//初始都给个0，有使用的置为1 
    
    	Product pros[n];
    	for (int i = 0; i < n; ++i)//初始化 
    	{
        
    		pros[i].id = i;
    		pros[i].w = w[i];
    		pros[i].v = v[i];
    	}
    
    	//按物品的性价比降序排列
    	sort(pros, pros + n, [](const Product& p1, const Product& p2)->bool {
        return p1 > p2; });
    
    	//按性价比高的往背包里面放（只考虑局部的最优解）
    	double bestv = 0.0;//记录背包的最大价值
    	for (int i = 0; i < n; ++i)
    	{
        
    		if (pros[i].w <= c)
    		{
         //说明第i个物品可以装入背包
    			bestv += pros[i].v;
    			c -= pros[i].w;
    		}
    		else
    		{
         //说明第i个物品无法全部装入背包，按剩余容量的比例装入物品的一部分
    			bestv = bestv + pros[i].v * (c * 1.0 / pros[i].w);
    			x[pros[i].id] = 1;
    			break;//说明已经装完了！！！
    		}
    
    		x[pros[i].id] = 1;
    	}
    
    	cout << "bestv:" << bestv << endl;
    	for (int v : x)
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;
    
    	return 0;
    }

**运行截图如下**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]

## 柜台提供服务问题 ##

**m个柜台提供服务，每个柜台给一个用户提供服务的时间是t(用数组表示每一个柜台提供服务的时间)，  
问怎么排列，使得柜台给所有用户提供服务的时间最少？**

**贪心算法**就是优先给给用户提供服务的时间的最少的柜台分配用户，然后再试着给其他的花费比较少时间的柜台分配用户

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    //定义柜台类 
    struct Counter 
    {
          //描述柜台
    	bool operator<(const Counter &counter) const//重载< 
    	{
        
    		return time < counter.time;
    	}
    	int id;//柜台id
    	int time;//柜台提供服务所花费的时间
    };
    
    int main()
    {
        
    	int arr[] = {
         3,2,4 };//每一个柜台处理每个用户所服务的时间
    	const int m = sizeof(arr) / sizeof(arr[0]);//柜台的数量 3
    	int n = 15;//办理业务的用户人数
    
    	//定义柜台信息数组，初始化柜台id和time
    	Counter cons[m];
    	for (int i = 0; i < m; ++i) 
    	{
        
    		cons[i].id = i;
    		cons[i].time = arr[i];
    	}
    
    	//按照柜台提供服务的时间升序排列
    	sort(cons, cons + m);//从小到大排序
    
    	int mintime = 0;//记录给所有用户提供服务的最少时间
    	int x[m] = {
         0 };//记录每一个柜台安排的用户数量
    
    	for (int i = 0; i < n; ++i)//遍历所有的用户 
    	{
        
    		//先计算把i用户放在0号柜台的时间，因为0号柜台提供服务的时间最快 
    		int time = cons[0].time * (x[0] + 1);//0号柜台的i用户之前的人在x[0]放着，不着急给x[0]++，我们只是假设先放在0号柜台
    		//因为不一定放在0柜台，有可能0号柜台人很多了，放在其他柜台效率还高呢
    		//再遍历其它的柜台，看是否可以得到更少的花费时间
    		int j = 1;
    		for (; j < m; ++j) 
    		{
        
    			int t = cons[j].time * (x[j] + 1);
    			if (t <= time) 
    			{
           //放在其它柜台处理时间总体更快，直接放入j柜台
    				x[j]++;
    				//新添加了一个人，整体花费的时间有可能变得更长了，更新mintime
    				if (t > mintime) 
    				{
        
    					mintime = t;
    				}
    				break;
    			}
    		}
    		//最终还是放在0号柜台花费时间最少
    		if (j == m) 
    		{
        
    			x[0]++;
    			//新添加了一个人，整体花费的时间有可能变得更长了，更新mintime
    			mintime = cons[0].time * x[0];
    		}
    	}
    
    	cout << mintime << endl;
    	for (int i = 0; i < m; ++i) 
    	{
        
    		cout << arr[cons[i].id] << " : " << x[i] << endl;
    	}
    
    	return 0;
    }

**运行截图如下**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/25f5c366ce2e4131a923a952f7e0d631.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/ea758c58e17d4c1eaef7a0027ef2313f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/5304a52092ae4b538e6d1aafbe40369d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20220829/d254b0e1a436436b852f06219f29d40d.png