C++ 算法精讲之贪心算法

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;
    }
};

买股票的最佳时机

问题描述：

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

贪心策略：

连续上涨交易日：第一天买最后一天卖收益最大，等价于每天都买卖。

连续下降交易日：不买卖收益最大，即不会亏钱。

故可以遍历整个股票交易日价格列表，在所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）

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;
    }
};

跳跃游戏

问题描述：

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

贪心策略：

根据题目描述，对于数组中的任意一个位置y，只要存在一个位置x，它本身可以到达，并且它跳跃的最大长度为x+nums[x]，这个值大于等于y，即x+nums[x] >= y，那么位置y也可以到达。即对于每一个可以到达的位置x，它使得x+1，x+2，…，x+nums[x] >= y，那么位置y也可以到达。 一次遍历数组中的每一个位置，并实时更新最远可以到达的位置。对于当前遍历到的位置x，如果它在最远可以到达的位置范围内，那么我们就可以从起点通过若干次跳跃达到该位置，因此我们可以用x+nums[x]更新最远可以到达的位置。

在遍历的过程中，如果最远可以到达的位置大于等于数组中的最后一个位置，那就说明最后一个位置可到达，直接返回true。遍历结束后，最后一个位置仍不可达，返回false。

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

一开始在位置0，可跳跃的最大长度为2，因此最远可以到达的位置倍更新为2；继续遍历到位置1，由于1<=2，因此位置1可达。用1加上它最大可跳跃的长度3，将最远可以到达的位置更新为4，4大于最后一个位置4，返回true

代码实现：

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;
    }
};

钱币找零

问题描述：

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

贪心策略： 显然，每一步尽可能用面值大的纸币即可。在日常生活中我们也是这么做的。

代码实现：

//按面值降序
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++)
	{
		//选择需要的当前面值和该面值有的数量中的较小值
		int c = min(money / moneyCount[i][0], moneyCount[i][1]);
		money -= c * moneyCount[i][0];
		num += c;
	}
	if (money > 0)
		num = -1;
	return num;
}

多机调度问题

问题描述：

某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的最短时间。

输入：第一行T（1<T<100)表示有T组测试数据。每组测试数据的第一行分别是整数n，m（1<=n<=10000，1<=m<=100），接下来的一行是n个整数ti（1<=t<=100)。

输出：所需的最短时间

贪心策略：

这个问题还没有最优解，但是用贪心选择策略可设计出较好的近似算法（求次优解） 当n<=m时，只要将作业分给每一个机器即可；当n>m时，首先将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);
}