用c语言写一个贪心算法

我可以给你一些提示，但具体的实现方式需要你自己去实现。贪心算法是一种常用的算法，其基本思想是在每一步选择中总是做出在当前看来是最佳的选择，从而希望最终能够达到全局最优解。在C语言中，可以使用循环和决策语句来实现贪心算法，比如使用 if-else 语句来比较多个候选项，从而实现选择最优解的过程。

相关问题

用C语言写一个贪心算法

以下是一个简单的使用贪心算法解决背包问题的C语言代码：

#include <stdio.h>

// 物品结构体
struct item {
    int value;  // 价值
    int weight; // 重量
};

// 按照价值密度从大到小排序
int cmp(const void* a, const void* b) {
    struct item* x = (struct item*)a;
    struct item* y = (struct item*)b;
    double r1 = (double)x->value / x->weight;
    double r2 = (double)y->value / y->weight;
    if (r1 < r2)
        return 1;
    else if (r1 > r2)
        return -1;
    else
        return 0;
}

// 使用贪心算法求解背包问题
double knapsack(struct item* items, int n, int capacity) {
    int i;
    double total_value = 0.0;
    qsort(items, n, sizeof(struct item), cmp); // 按照价值密度排序
    for (i = 0; i < n; i++) {
        if (items[i].weight <= capacity) { // 如果物品可以完全装入背包
            total_value += items[i].value;
            capacity -= items[i].weight;
        } else { // 如果物品不能完全装入背包
            total_value += (double)items[i].value / items[i].weight * capacity;
            break;
        }
    }
    return total_value;
}

int main() {
    struct item items[] = {{60, 10}, {100, 20}, {120, 30}};
    int n = sizeof(items) / sizeof(struct item);
    int capacity = 50;
    double result = knapsack(items, n, capacity);
    printf("Total value: %.2f\n", result);
    return 0;
}

以上代码使用了一个结构体来表示物品，其中包含了物品的价值和重量。在贪心算法中，我们首先按照物品的价值密度（即单位重量的价值）从大到小排序，然后依次将物品装入背包中，直到背包无法再装入任何物品为止。如果当前物品可以完全装入背包中，则将其完全装入；否则只装入部分，使得背包恰好装满。最终返回背包中物品的总价值。

用c语言写一个贪心算法例子

下面是一个使用贪心算法求解活动安排问题的C语言代码示例：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start;
    int end;
} Activity;

int cmp(const void *a, const void *b) {
    Activity *act1 = (Activity*)a;
    Activity *act2 = (Activity*)b;
    return act1->end - act2->end;
}

void selectActivities(Activity activities[], int n) {
    qsort(activities, n, sizeof(Activity), cmp);

    int i = 0, j;
    printf("Selected activities: %d ", i);

    for (j = 1; j < n; j++) {
        if (activities[j].start >= activities[i].end) {
            printf("%d ", j);
            i = j;
        }
    }
}

int main() {
    Activity activities[] = {
        {1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}
    };
    int n = sizeof(activities) / sizeof(activities[0]);

    selectActivities(activities, n);

    return 0;
}

该代码演示了如何使用贪心算法解决活动安排问题。首先，将所有活动按照结束时间从小到大排序，然后从第一个活动开始，依次选择结束时间比上一个活动开始时间晚的活动，直到遍历完所有活动。在选择过程中，输出已选择的活动的下标。