什么是贪心算法?
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。不从整体
最优上加以考虑,他所做出的是在某种意义上的局部最优解。
举个例子:
你现在非常非常饿, 去食堂买了5,6个菜。每次都优先吃完最好吃的那一份菜,然后算吃完所有的菜。
你的任务:就是吃完所有的菜。 解决问题的方式:优先吃最好吃的。
为什么说它是一种贪心算法呢?
因为每次都是选择最大值或者最小值以达到排序的目的。
下面代码可以适度优化一下,同时找最小值和最大值,放在数组的两端。
不过要注意的是,交换的时候可能会出现 “位置重叠”
代码:
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.
为什么是贪心算法呢? 因为只考虑局部,不用考虑整体。
也就是说,我每遇到一对平衡字符串,则计数加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;
}
};
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;
}
};
为什么跳跃游戏是贪心呢?
因为只用考虑当前下标位置跳跃的最远距离,能不能跳过整个数组。
通过一列当前位置的跳跃来求解总问题。
代码:
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元、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;
}
某工厂有n个独立的作业,由m台相同的机器进行加工处理。作业i所需的加工时间为ti,任何作业在被处理时不能中
断,也不能进行拆分处理。现厂长请你给他写一个程序:算出n个作业由m台机器加工处理的最短时间
输入
第一行T(1
解题思路:
分两种情况
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;
}