• 算法篇------贪心1


    贪心的概念

    什么是贪心算法?
    贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择不从整体
    最优上加以考虑
    ,他所做出的是在某种意义上的局部最优解

    举个例子:
    你现在非常非常饿, 去食堂买了5,6个菜。每次都优先吃完最好吃的那一份菜,然后算吃完所有的菜。
    你的任务:就是吃完所有的菜。 解决问题的方式:优先吃最好吃的。

    题目1------经典的选择排序(简单)

    为什么说它是一种贪心算法呢?
    因为每次都是选择最大值或者最小值以达到排序的目的。

    下面代码可以适度优化一下,同时找最小值和最大值,放在数组的两端。
    不过要注意的是,交换的时候可能会出现 “位置重叠”
    代码:

    void SelectSort(int* arr, int n)
    {
    	for (int i = 0; i < n; i++)
    	{
    		int maxi = i;
    		for (int j = i + 1; j < n; j++)
    		{
    			if (arr[maxi] < arr[j])
    				maxi = j;
    		}
    
    		swap(arr[i], arr[maxi]);
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    题目2----平衡字符串(简单)

    力扣:平衡字符串
    解题思路:优先遇到平衡则计数加1.
    为什么是贪心算法呢? 因为只考虑局部,不用考虑整体。
    也就是说,我每遇到一对平衡字符串,则计数加1。

    代码:

    class Solution 
    {
    public:
        int balancedStringSplit(string s) 
        {
            int balance = 0, count = 0;
            for(int i = 0; i < s.size(); i++)
            {
                if(s[i] == 'R')
                   balance++;
                else
                   balance--;
    
                if(balance == 0)
                  count++;
            }
            
            return count;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    题目3—买卖股票的最佳时间(中等)

    在这里插入图片描述

    class Solution {
    public:
        int maxProfit(vector<int>& prices) 
        {
            int maxprofit = 0;
            for(int i = 0; i < prices.size() - 1; i++)
            {
                if(prices[i] < prices[i + 1])
                {
                    maxprofit += prices[i + 1] - prices[i];
                }
            }
            
            return maxprofit;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    题目4------跳跃游戏(中等)

    力扣:跳跃游戏

    为什么跳跃游戏是贪心呢?
    因为只用考虑当前下标位置跳跃的最远距离,能不能跳过整个数组。
    通过一列当前位置的跳跃来求解总问题。

    代码:

    class Solution {
    public:
        bool canJump(vector<int>& nums) 
        {
            int len = nums.size();
            int maxdis = 0; //定义的下标位置
    
            for(int i = 0; i < len; i++)
            {
                if(i <= maxdis) // 表示可以到达下标i的位置,如果不能到达就没有必要了
                {
                      maxdis = max(maxdis, i + nums[i]);
                }
    
                if(maxdis >= len - 1)
                   return true;
            }
    
             return false;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    题目5-------钱币找零

    假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K
    元,至少要用多少张纸币?

    为什么是贪心呢?
    每次都找到最大面额的钱,通过一系列局部的最优解来解决总问题

    class Sort
    {
    public:
    	bool operator()(vector<int> a, vector<int> b)
    	{
    		return a[0] > b[0];         //按照二维数组中一维数组第一个元素排升序
    	}
    };
    
    int get_money_num(const vector<vector<int>>& vv, int money)
    {
    	int num = 0;	
    	for (int i = 0; i < vv.size(); i++)
        {
    	   int cnt = min(money / vv[i][0], vv[i][1]);
    	   money -= cnt * vv[i][0];
    	   num += cnt;
    
    	   if (money == 0)
    		   return num;
    	}	
    
    	return -1;
    }
    
    int main()
    {
    	vector<vector<int>> vv = { {10,5}, {100,4}, {20, 3} , {5, 6}, {1, 10}, {50,5 } };
    	sort(vv.begin(), vv.end(), Sort());  
    
    	int money = 0;
    	while (cin >> money)
    	{
    		int ret = get_money_num(vv, money);
    
    		if (ret == -1)
    		{
    			cout << "无法找零" << endl;
    		}
    		else
    		{
    			cout << ret << endl;
    		}
    	}
    
    	return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    题目6------多机调度的问题

    某工厂有n个独立的作业,由m台相同的机器进行加工处理。作业i所需的加工时间为ti,任何作业在被处理时不能中
    断,也不能进行拆分处理。现厂长请你给他写一个程序:算出n个作业由m台机器加工处理的最短时间
    输入
    第一行T(1 1<=m<=100),接下来的一行是n个整数ti(1<=t<=100)。

    解题思路:
    分两种情况
    1, m >= n 取n个作业中执行时间最长的即可
    2, m < n 先将 m 个作业分配给m个机器, 然后每次从剩余的作业中找到最长执行时间的
    作业,将它分配给m个机器中耗时最小的哪个机器。
    例如:

    在这里插入图片描述

    为什么是贪心呢? 因为每次都需要去找最长时间的作业放到最快执行完的机器中。
    通过一系列的局部最优达到总体最优。

    代码分享:

    //数组v以按降序排列
    int get_min_time(vector<int>& v, int n, int m)
    {
    	if (n <= m)
    	{
    		return v[0];
    	}
    
    	vector<int> ans( v.begin(), v.begin() + m);
    
    	for (int i = m; i < v.size(); i++)
    	{
    		int minindex = 0;  //每次找到耗费时间最少的哪个机器下标
    		for (int j = 1; j < m; j++)
    		{
    			if (ans[j] < ans[minindex])
    				minindex = j;
    		}
    
    		ans[minindex] += v[i];
    	}
    
    	int max = ans[0];
    	for (int i = 1; i < m; i++)
    	{
    		if (ans[i] > max)
    			max = ans[i];
    	}
    
    	return max;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
  • 相关阅读:
    react中使用jquery 语法
    【JS】判断水仙花数
    【LeetCode: 901. 股票价格跨度 | 单调栈】
    AEB前装搭载率逼近50%,沃尔沃「标配」激光雷达释放信号
    HTML5:七天学会基础动画网页7
    轻量级DI框架Guice使用详解
    Truenas scale 配置Zerotier
    js 生成随机数(含随机颜色)
    socket套接字——UDP协议
    卧兔网络开启全球红人分销功能,WotoHub上线Shopify应用商店!
  • 原文地址:https://blog.csdn.net/CL2426/article/details/127857535