c语言贪心算法（c语言贪心算法背包问题）

# C语言贪心算法## 简介贪心算法是一种在每个步骤中都采取局部最优解以期望达到全局最优解的算法设计方法。它是一种简单且高效的算法策略，广泛应用于优化问题中。C语言作为一种高效且灵活的编程语言，非常适合用来实现贪心算法。本文将详细介绍C语言中的贪心算法概念、实现方式以及一些经典案例。## 贪心算法的基本原理### 局部最优解贪心算法的核心在于每次选择当前状态下最优的选择，从而希望最终得到全局最优解。这种策略通常适用于那些具有“最优子结构”和“无后效性”的问题。### 适用范围贪心算法通常用于解决以下几类问题： -

最优化问题

：如最小生成树、最短路径等。 -

分配问题

：如任务调度、资源分配等。 -

组合问题

：如背包问题、集合覆盖问题等。## 贪心算法的经典案例### 活动选择问题#### 问题描述假设有多个活动，每个活动都有一个开始时间和结束时间。如何选择尽可能多的不冲突的活动？#### 解决方案1. 对所有活动按结束时间排序。 2. 从第一个活动开始选择，然后依次选择与已选活动不冲突的下一个活动。```c #include #include // 定义活动结构体 struct Activity {int start;int end; };// 按结束时间排序 int compare(const void

a, const void

b) {struct Activity

act1 = (struct Activity

)a;struct Activity

act2 = (struct Activity

)b;return act1->end - act2->end; }void printMaxActivities(struct Activity arr[], int n) {int i, j;// 选择第一个活动printf("%d ", 0);for (i = 1, j = 0; i < n; i++) {if (arr[i].start >= arr[j].end) {printf("%d ", i);j = i;}} }int main() {struct Activity arr[] = {{1, 3}, {2, 5}, {4, 6}, {6, 8}, {9, 10}};int n = sizeof(arr) / sizeof(arr[0]);qsort(arr, n, sizeof(struct Activity), compare);printMaxActivities(arr, n);return 0; } ```### 背包问题#### 问题描述给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择物品使得总价值最大？#### 解决方案采用贪心算法时，优先选择单位重量价值最大的物品。```c #include #include // 定义物品结构体 struct Item {int value;int weight; };// 按单位重量价值排序 int compare(const void

a, const void

b) {double r1 = ((struct Item

)a)->value / ((struct Item

)a)->weight;double r2 = ((struct Item

)b)->value / ((struct Item

)b)->weight;return (r1 < r2) ? 1 : -1; }double fractionalKnapsack(int W, struct Item arr[], int n) {double finalvalue = 0.0;// 按单位重量价值排序qsort(arr, n, sizeof(struct Item), compare);for (int i = 0; i < n; i++) {if (arr[i].weight <= W) {W -= arr[i].weight;finalvalue += arr[i].value;} else {finalvalue += arr[i].value

((double)W / arr[i].weight);break;}}return finalvalue; }int main() {int W = 50;struct Item arr[] = {{60, 10}, {100, 20}, {120, 30}};int n = sizeof(arr) / sizeof(arr[0]);printf("Maximum value we can obtain = %.2lf\n", fractionalKnapsack(W, arr, n));return 0; } ```## 总结贪心算法以其简洁高效的特点，在C语言编程中有着广泛的应用。通过本文介绍的活动选择问题和背包问题，我们可以看到贪心算法在解决最优化问题上的强大能力。然而，需要注意的是，并非所有问题都能用贪心算法求得全局最优解，因此在使用时需要仔细分析问题特性。

C语言贪心算法

简介贪心算法是一种在每个步骤中都采取局部最优解以期望达到全局最优解的算法设计方法。它是一种简单且高效的算法策略，广泛应用于优化问题中。C语言作为一种高效且灵活的编程语言，非常适合用来实现贪心算法。本文将详细介绍C语言中的贪心算法概念、实现方式以及一些经典案例。

贪心算法的基本原理

局部最优解贪心算法的核心在于每次选择当前状态下最优的选择，从而希望最终得到全局最优解。这种策略通常适用于那些具有“最优子结构”和“无后效性”的问题。

适用范围贪心算法通常用于解决以下几类问题： - **最优化问题**：如最小生成树、最短路径等。 - **分配问题**：如任务调度、资源分配等。 - **组合问题**：如背包问题、集合覆盖问题等。

贪心算法的经典案例

活动选择问题

问题描述假设有多个活动，每个活动都有一个开始时间和结束时间。如何选择尽可能多的不冲突的活动？

解决方案1. 对所有活动按结束时间排序。 2. 从第一个活动开始选择，然后依次选择与已选活动不冲突的下一个活动。```c

include

include // 定义活动结构体 struct Activity {int start;int end; };// 按结束时间排序 int compare(const void *a, const void *b) {struct Activity *act1 = (struct Activity *)a;struct Activity *act2 = (struct Activity *)b;return act1->end - act2->end; }void printMaxActivities(struct Activity arr[], int n) {int i, j;// 选择第一个活动printf("%d ", 0);for (i = 1, j = 0; i < n; i++) {if (arr[i].start >= arr[j].end) {printf("%d ", i);j = i;}} }int main() {struct Activity arr[] = {{1, 3}, {2, 5}, {4, 6}, {6, 8}, {9, 10}};int n = sizeof(arr) / sizeof(arr[0]);qsort(arr, n, sizeof(struct Activity), compare);printMaxActivities(arr, n);return 0; } ```

背包问题

问题描述给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择物品使得总价值最大？

解决方案采用贪心算法时，优先选择单位重量价值最大的物品。```c

include

include // 定义物品结构体 struct Item {int value;int weight; };// 按单位重量价值排序 int compare(const void *a, const void *b) {double r1 = ((struct Item *)a)->value / ((struct Item *)a)->weight;double r2 = ((struct Item *)b)->value / ((struct Item *)b)->weight;return (r1 < r2) ? 1 : -1; }double fractionalKnapsack(int W, struct Item arr[], int n) {double finalvalue = 0.0;// 按单位重量价值排序qsort(arr, n, sizeof(struct Item), compare);for (int i = 0; i < n; i++) {if (arr[i].weight <= W) {W -= arr[i].weight;finalvalue += arr[i].value;} else {finalvalue += arr[i].value * ((double)W / arr[i].weight);break;}}return finalvalue; }int main() {int W = 50;struct Item arr[] = {{60, 10}, {100, 20}, {120, 30}};int n = sizeof(arr) / sizeof(arr[0]);printf("Maximum value we can obtain = %.2lf\n", fractionalKnapsack(W, arr, n));return 0; } ```

总结贪心算法以其简洁高效的特点，在C语言编程中有着广泛的应用。通过本文介绍的活动选择问题和背包问题，我们可以看到贪心算法在解决最优化问题上的强大能力。然而，需要注意的是，并非所有问题都能用贪心算法求得全局最优解，因此在使用时需要仔细分析问题特性。