C++ 算法精講之貪心算法

更新時間：2022年03月24日 16:57:47 作者：ymz123_

貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解

選擇排序

我們熟知的選擇排序，其采用的就是貪心策略。它所采用的貪心策略即為每次從未排序的數(shù)據(jù)中選取最小值，并把最小值放在未排序數(shù)據(jù)的起始位置，直到未排序的數(shù)據(jù)為0，則結(jié)束排序。

void swap(int* arr, int i, int j)
{
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

void selectSort(int* arr, int n)
{
	//降序
	for (int i = 0; i < n; i++)
	{
		int maxIndex = i;
		for (int j = i+1; j < n; j++)
		{
			if (arr[j] >= arr[maxIndex])
				maxIndex = j;
		}
		swap(arr, i, maxIndex);
	}
}

平衡字符串

問題描述：

在一個平衡字符串中，‘L' 和 ‘R' 字符的數(shù)量是相同的。

給你一個平衡字符串 s，請你將它分割成盡可能多的平衡字符串。

注意：分割得到的每個字符串都必須是平衡字符串，且分割得到的平衡字符串是原平衡字符串的連續(xù)子串。

返回可以通過分割得到的平衡字符串的最大數(shù)量。

貪心策略：從左往右掃描，只要達到平衡，就立即分割，不要有嵌套的平衡。

故可以定義一個變量balance，在遇到不同的字符時，向不同的方向變化，當(dāng)balance為0時達到平衡，分割數(shù)更新。

比如：從左往右掃描字符串s，遇到L，balance-1，遇到R，balance+1.當(dāng)balance為0時，更新cnt++ 如果最終cnt==0，說明s只需要保持原樣，返回1

代碼實現(xiàn)：

class Solution {
public:
    int balancedStringSplit(string s) {
        if(s.size() == 1)
            return 0;
        int cnt = 0;
        int balance = 0;
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == 'R')
                --balance;
            else 
                ++balance;
            if(balance == 0)
                cnt++;
        }
        if(cnt == 0)
            return 1;

        return cnt;
    }
};

買股票的最佳時機

問題描述：

給定一個數(shù)組 prices ，其中 prices[i] 是一支給定股票第 i 天的價格。

設(shè)計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

貪心策略：

連續(xù)上漲交易日：第一天買最后一天賣收益最大，等價于每天都買賣。

連續(xù)下降交易日：不買賣收益最大，即不會虧錢。

故可以遍歷整個股票交易日價格列表，在所有上漲交易日都買賣（賺到所有利潤），所有下降交易日都不買賣（永不虧錢）

例如從10到50是連續(xù)上漲的5天，可以第一天買入，最后一天賣出，利潤為40，等價于第一天買入第二天賣出，第二天再買入。。。以此類推

代碼實現(xiàn)：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for(int i = 0; i < prices.size() - 1; i++)
        {
            if(prices[i] <= prices[i+1])
                profit += prices[i+1] - prices[i];
        }

        return profit;
    }
};

跳躍游戲

問題描述：

給定一個非負整數(shù)數(shù)組 nums ，你最初位于數(shù)組的第一個下標(biāo) 。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最后一個下標(biāo)。

貪心策略：

根據(jù)題目描述，對于數(shù)組中的任意一個位置y，只要存在一個位置x，它本身可以到達，并且它跳躍的最大長度為x+nums[x]，這個值大于等于y，即x+nums[x] >= y，那么位置y也可以到達。即對于每一個可以到達的位置x，它使得x+1，x+2，…，x+nums[x] >= y，那么位置y也可以到達。一次遍歷數(shù)組中的每一個位置，并實時更新最遠可以到達的位置。對于當(dāng)前遍歷到的位置x，如果它在最遠可以到達的位置范圍內(nèi)，那么我們就可以從起點通過若干次跳躍達到該位置，因此我們可以用x+nums[x]更新最遠可以到達的位置。

在遍歷的過程中，如果最遠可以到達的位置大于等于數(shù)組中的最后一個位置，那就說明最后一個位置可到達，直接返回true。遍歷結(jié)束后，最后一個位置仍不可達，返回false。

例如：[2, 3, 1, 1, 4]

一開始在位置0，可跳躍的最大長度為2，因此最遠可以到達的位置倍更新為2；繼續(xù)遍歷到位置1，由于1<=2，因此位置1可達。用1加上它最大可跳躍的長度3，將最遠可以到達的位置更新為4，4大于最后一個位置4，返回true

代碼實現(xiàn)：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxLen = nums[0];
        for(int i = 0; i < nums.size(); i++)
        {
            if(i <= maxLen)
            {
                maxLen = max(i + nums[i],maxLen);
                if(maxLen >= nums.size() - 1)
                    return true;
            }
        }

        return false;
    }
};

錢幣找零

問題描述：

假設(shè)1元、2元、5元、10元、20元、50元、100元的紙幣分別有c0, c1, c2, c3, c4, c5, c6張?，F(xiàn)在要用這些錢來支付K元，至少要用多少張紙幣？

貪心策略：顯然，每一步盡可能用面值大的紙幣即可。在日常生活中我們也是這么做的。

代碼實現(xiàn)：

//按面值降序
struct cmp {
	bool operator()(vector<int>& a1, vector<int>& a2) {
		return a1[0] > a2[0];
	}
};

int solve(vector<vector<int>>& moneyCount, int money)
{
	int num = 0;
	sort(moneyCount.begin(), moneyCount.end(), cmp());
	//首先選擇最大面值的紙幣
	for (int i = 0; i < moneyCount.size() - 1; i++)
	{
		//選擇需要的當(dāng)前面值和該面值有的數(shù)量中的較小值
		int c = min(money / moneyCount[i][0], moneyCount[i][1]);
		money -= c * moneyCount[i][0];
		num += c;
	}
	if (money > 0)
		num = -1;
	return num;
}

多機調(diào)度問題

問題描述：

某工廠有n個獨立的作業(yè)，由m臺相同的機器進行加工處理。作業(yè)i所需的加工時間為ti，任何作業(yè)在被處理時不能中斷，也不能進行拆分處理。現(xiàn)廠長請你給他寫一個程序：算出n個作業(yè)由m臺機器加工處理的最短時間。

輸入：第一行T（1<T<100)表示有T組測試數(shù)據(jù)。每組測試數(shù)據(jù)的第一行分別是整數(shù)n，m（1<=n<=10000，1<=m<=100），接下來的一行是n個整數(shù)ti（1<=t<=100)。

輸出：所需的最短時間

貪心策略：

這個問題還沒有最優(yōu)解，但是用貪心選擇策略可設(shè)計出較好的近似算法（求次優(yōu)解）當(dāng)n<=m時，只要將作業(yè)分給每一個機器即可；當(dāng)n>m時，首先將n個作業(yè)時間從大到小排序，然后依此順序?qū)⒆鳂I(yè)分配給下一個作業(yè)馬上結(jié)束的處理機。也就是說從剩下的作業(yè)中選擇需要處理時間最長的，然后依次選擇處理時間次長的，直到所有作業(yè)全部處理完畢，或者機器不能再處理其他作業(yè)為止。如果我們每次是將需要處理時間最短的作業(yè)分配給空閑的機器，那么可能就會儲秀安其它所有作業(yè)都處理完了只剩下所需時間最長的作業(yè)在處理的情況，這樣勢必效率較低。

代碼實現(xiàn)：

struct cmp{
	bool operator()(const int& x, const int& y){
		return x > y;
	}
};

int findMax(vector<int>& machines)
{
	int ret = 0;
	for (int i = 0; i < machines.size(); i++)
	{
		if (machines[i] > machines[ret])
			ret = i;
	}

	return machines[ret];
}

int greedStrategy(vector<int>& works, vector<int>& machines)
{
	//降序
	sort(works.begin(), works.end(), cmp());
	int n = works.size();
	int m = machines.size();
	for (int i = 0; i < n; i++)
	{
		int finish = 0;
		int machineTime = machines[finish];
		for (int j = 1; j < m; j++)
		{
			if (machines[j] < machines[finish])
			{
				finish = j;
			}
		}
		machines[finish] += works[i];
	}

	return findMax(machines);
}

活動選擇

問題描述：

有n個需要在同一天使用同一個教室的活動a1, a2, …, an，教室同一時刻只能由一個活動使用。每個活動a[i]都有一個開始時間s[i]和結(jié)束時間f[i]。一旦被選擇后，活動a[i]就占據(jù)半開時間區(qū)間[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重疊，a[i]和a[j]兩個活動就可以被安排在這一天。求使得盡量多的活動能不沖突的舉行的最大數(shù)量。

貪心策略：

1.每次都選擇開始時間最早的活動，不能得到最優(yōu)解。

2.每次都選擇持續(xù)時間最短的活動，不能得到最優(yōu)解。

3.每次選取結(jié)束時間最早的活動（結(jié)束時間最早意味著開始時間也早），可以得到最優(yōu)解。按這種方法選擇，可以為未安排的活動留下盡可能多的時間。如下圖的活動集合S，其中各項活動按照結(jié)束時間單調(diào)遞增排序。

代碼實現(xiàn)：

struct cmp{
	bool operator()(vector<int>& s1, vector<int>& s2){
		return s1[1] < s2[1];
	}
};

int getMaxNum(vector<vector<int>>& events)
{
	sort(events.begin(), events.end(), cmp());
	int num = 1;
	int i = 0;
	for (int j = 1; j < events.size();j++)
	{
		if (events[j][0] >= events[i][1])
		{
			++num;
			i = j;
		}
	}

	return num;
}

無重疊區(qū)間

問題描述：

給定一個區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。

注意:

可以認為區(qū)間的終點總是大于它的起點。

區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。

貪心策略：

法一：與上題活動選擇類似，用總區(qū)間數(shù)減去最大可同時進行的區(qū)間數(shù)即為結(jié)果。

法二：當(dāng)按照起點先后順序考慮區(qū)間時，利用一個prev指針追蹤剛剛添加到最終列表中的區(qū)間。遍歷時，可能遇到三種情況：

情況1：當(dāng)前考慮的兩個區(qū)間不重疊。這種情況下不移除任何區(qū)間，將prev賦值為后面的區(qū)間，移除區(qū)間數(shù)量不變。

情況2：兩個區(qū)間重疊，后一個區(qū)間的終點在前一個區(qū)間的終點之前。由于后一個區(qū)間的長度更小，可以留下更多空間，容納更多區(qū)間，將prev更新為當(dāng)前區(qū)間，移除區(qū)間的數(shù)量+1

情況3：兩個區(qū)間重疊，后一個區(qū)間的終點在前一個區(qū)間的終點之后。直接移除后一個區(qū)間，留下更多空間。因此，prev不變，移除區(qū)間的數(shù)量+1

代碼實現(xiàn)：法一：

struct cmp{
	bool operator()(vector<int>& s1, vector<int>& s2){
		return s1[1] < s2[1];
	}
};

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp());
        int num = 1;
        int i = 0;
        for(int j = 1; j < intervals.size(); j++)
        {
            if(intervals[j][0] >= intervals[i][1])
            {
                i = j;
                num++;
            }
        }

        return intervals.size() - num;
    }
};

法二：

struct cmp{
	bool operator()(vector<int>& s1, vector<int>& s2){
		return s1[1] < s2[1];
	}
};

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty())
            return 0;
        sort(intervals.begin(), intervals.end(), cmp());
        int prev = 0;
        int num = 0;
        for(int i = 1; i < intervals.size(); i++)
        {
            //情況1 不沖突
            if(intervals[i][0] >= intervals[prev][1])
            {
                prev = i;
            }
            else
            {
                if(intervals[i][1] < intervals[prev][1])
                {
                    //情況2
                    prev = i;
                }
                num++;
            }
        }

        return num;
    }
};

到此這篇關(guān)于C++ 算法精講之貪心算法的文章就介紹到這了,更多相關(guān)C++ 貪心算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: