贪心算法几个经典例子代码c++代码
贪心算法是一种常见的解决优化问题的算法，其思路是每次选择局部最优的策略，来达到最终的全局最优解。在实际的问题中，贪心算法的应用非常广泛，比如字典序最小问题、背包问题、活动选择问题等等。这里我们将针对贪心算法的几个经典例子进行详细的讲解，并提供C++代码供读者参考。
一、字典序最小问题
字典序最小问题是指，给定一个字符串s，求出其长度为k的子串中字典序最小的那个子串。贪心算法解决这个问题的过程如下：
1. 如果k=1，则直接取s中第一个字符作为结果。
2. 如果k>1，则从左到右遍历字符串s，每次取字典序最小的还未被选中的字符。需要注意的是，如果s中剩余的字符数小于k，则不能继续循环，要返回已选择的字符。
下面是该问题的C++代码实现：
```cpp
string getMinSubstr(string s, int k) {
string res = "";
int n = s.size();
for (int i = 0; i < n && k; i++) {
char c = s[i];
int j = i + 1;
for (; j < n && j - i < k; j++) {
if (s[j] < c)
c = s[j];
}
res += c;
k--;
if (n - j < k)
break;
while (i + 1 < j && s[i] == c)
i++;
}
return res;
}
```
二、背包问题
背包问题是指，有一个容量为v的背包，以及n个物品，每个物品有自己的体积和价值。要求从这n个物品中选出总体积不超过v的物品，使得它们的总价值最大。
贪心算法解决这个问题的思路是，每次选择当前价值最高的物品装入背包。但是这种贪心策略不一定能得到最优解，因为在有些情况下，某个物品的体积较大，而其价值收益较小，因此不选该物品反而能够得到更高的总价值。
下面是背包问题的C++代码实现：
```cpp
struct Node {
int v, w;
bool operator<(const Node& a) const {
return w * a.v > a.w * v;
}
};
double knapsack(vector
double res = 0.0;
sort(nodes.begin(), nodes.end());
for (int i = 0; i < nodes.size() && v > 0; i++) {
if (v > nodes[i].v) {
res += nodes[i].w;
v -= nodes[i].v;
}
else {
res += nodes[i].w * v / double(nodes[i].v);
break;
}
}
return res;
}
```
三、活动选择问题
活动选择问题是指，有n个活动，每个活动有开始时间si和结束时间fi，选择一些活动使得它们之间没有冲突，且所选活动数目最多。
贪心算法解决这个问题的思路是，每次选择最早结束的活动，并将该活动删除后，继续操作，直到所有的活动均已删除。
下面是活动选择问题的C++代码实现：
```cpp
struct Activity {
int s, f;
bool operator<(const Activity& a) const {
return f < a.f;
}
};
int activitySelection(vector
int res = 0, cur = 0;
sort(activities.begin(), activities.end());
for (int i = 0; i < activities.size(); i++) {
if (activities[i].s >= cur) {
res++;
cur = activities[i].f;
}
}
return res;
}
```
综上所述，贪心算法是一种简单而常用的算法，可以解决许多优化问题。但是需要注意的是，贪心算法并不是在所有情况下都能得到最优解，有些问题需要使用其他更为复杂的算法进行求解。
