浅析C语言贪心算法
前言
贪心算法的定义： 贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。 解题的一般步骤是： 1.建立数学模型来描述问题； 2.把求解的问题分成若干个子问题； 3.对每一子问题求解，得到子问题的局部最优解； 4.把子问题的局部最优解合成原来问题的一个解。 如果大家比较了解动态规划，就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。
提示：以下是本篇文章正文内容，下面案例可供参考
一、是什么？
贪心算法的定义： 贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
二、使用步骤
解题的一般步骤是： 1.建立数学模型来描述问题； 2.把求解的问题分成若干个子问题； 3.对每一子问题求解，得到子问题的局部最优解； 4.把子问题的局部最优解合成原来问题的一个解。
三、贪心算法案例
3.1背包问题：
先给大家介绍一下这个问题，就是给你一个背包，背包容量有限，但现在你要用这个背包去装一些物品，但这些物品价值不同，有的价值高，有的价值低，但我们想要尽可能的提升这个】背包的价值，所以我们要装一些价值更高的东西。
比如下面这个题：装满宝藏的藏宝洞。藏宝洞里面有 N(N≤100)N(N≤100) 堆金币，第 N堆金币的总重量和总价值分别是 x。有一个承重量为 N(N≤1000)T(T≤1000) 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问最多可以拿走多少价值的金币？
下面我给出这个题的代码：
#include<stdio.h>
struct stu {
int weight;
int price;
double prices;
};
double tanxin(struct stu* arr, int N,int T) {
double bag = T * 1.00;
double all_weight = 0.0,all_price=0.0;
double diff_weight = 0.0;
for (int i = 0; i < N; i++) {
all_weight += arr[i].weight;
if (all_weight <= bag) {
all_price += arr[i].price;
}
if(all_weight > bag) {
diff_weight = arr[i].weight-(all_weight-bag);
all_price += diff_weight / arr[i].weight * arr[i].price;
break;
}
}
return all_price;
}
int main()
{
int N, T;
scanf("%d%d", &N, &T);
struct stu arr[10000] = {0};
for (int i = 0; i < N; i++) {
scanf("%d%d", &arr[i].weight,&arr[i].price);
}
for (int i = 0; i < N; i++) {
arr[i].prices = arr[i].price*1.00 / arr[i].weight;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N - 1 - i; j++) {
if (arr[j].prices< arr[j+1].prices) {
struct stu temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
double all_price = tanxin(arr, N,T);
printf("%.2lf\n", all_price);
return 0;
}3.2活动选择问题
这个问题就是我们要去参加几个活动，但是这几个活动在时间上可能会发生冲突，所以我们要尽可能的多参加，这时就可以用贪心算法来求最多可以参加多少个活动。
例如下面这道题（例子来自洛谷）
下面是这道题的代码：
#include<stdio.h>
#include<stdlib.h>
struct stu {
int begin;
int finish;
};
int cmp(const void* a, const void* b) {
struct stu* s1 = (struct stu*)a;
struct stu* s2 = (struct stu*)b;
if (s1->finish < s2->finish)
return -1;
else if (s1->finish > s2->finish)
return 1;
else
return 0;
}
int main()
{
int n = 0;
scanf("%d", &n);
struct stu *arr = (struct stu*)malloc(n * sizeof(struct stu));
for (int i = 0; i < n; i++) {
scanf("%d%d", &arr[i].begin, &arr[i].finish);
}
qsort(arr, n, sizeof(struct stu), cmp);
int count = 1;
int i = 0; int k = 1;
while (k<n) {
if (arr[i].finish <= arr[k].begin) {
count++;
i++;
arr[i].finish = arr[k].finish;
k++;
}
else {
k++;
}
}
printf("%d\n", count);
free(arr);
arr = NULL;
return 0;
}大家可以简单看一下这两道题。
总结
这篇文章我简单介绍了贪心算法，真的只是简单介绍，大佬们可以划走了，但这篇文章对新手还是会有很多帮助的，希望这篇文章可以为广大算法新手们的深入学习打好基础。