写一个贪心算法C语言实现

### 回答1：

/* 贪心算法C语言实现 */
#include <stdio.h>

// 定义最大数组长度
#define MAX 100

// 求解背包问题
void knapsack(int n, float weight[], float profit[], float capacity) {
float x[MAX], tp = 0;
int i, j, u;
u = capacity;

// 初始化
for (i = 0; i < n; i++)
x[i] = 0.0;

// 遍历物品
for (i = 0; i < n; i++) {
// 检查背包容量是否足以装入更多物品
if (weight[i] > u)
break;
else {
// 将物品装入背包
x[i] = 1.0;
tp = tp + profit[i];
u = u - weight[i];
}
}

// 物品i放置于背包中的部分容量
if (i < n)
x[i] = u / weight[i];

// 计算最大收益
tp = tp + (x[i] * profit[i]);

printf("最大利润：%f\n", tp);

// 打印物品放入情况
for (i = 0; i < n; i++)
printf("物品 %d 放入 %f\n", i + 1, x[i]);
}

// 主函数
int main() {
int n = 5;
float weight[] = {3, 2, 5, 7, 1};
float profit[] = {10, 5, 15, 7, 6};
float capacity = 15;

knapsack(n, weight, profit, capacity);

return 0;
}

### 回答2：
贪心算法是一种解决问题的策略，常用于在每一步选择中都采取当前状态下最优的选择，以期望能够获得全局最优解。以下是一个使用C语言实现贪心算法的示例：

假设有一个背包，它的容量为C，同时有n个物品，每个物品有两个属性：重量为weight[i]，价值为value[i]。要求我们从这些物品中选择一些放入背包，使得背包里物品的总价值最大。

思路：
1. 计算每个物品的单位重量价值：unit_value[i] = value[i] / weight[i]。
2. 按照物品的单位重量价值进行降序排序，使得单位重量价值最高的物品排在前面。
3. 依次按照降序排列的物品顺序，将能够放入背包且单位重量价值最高的物品放入背包，直到背包无法再容纳任何物品为止。

以下是C语言实现的代码：

#include <stdio.h>

void swap(double *a, double *b) {
double temp = *a;
*a = *b;
*b = temp;
}

void sort(double *w, double *v, double *u, int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (u[j] < u[j + 1]) {
swap(&w[j], &w[j + 1]);
swap(&v[j], &v[j + 1]);
swap(&u[j], &u[j + 1]);
}
}
}
}

double knapsack(double *w, double *v, int n, double c) {
int i;
double total_value = 0.0;
double remaining_capacity = c;
double unit_value[n];

for (i = 0; i < n; i++) {
unit_value[i] = v[i] / w[i];
}

sort(w, v, unit_value, n);

for (i = 0; i < n; i++) {
if (remaining_capacity >= w[i]) {
total_value += v[i];
remaining_capacity -= w[i];
} else {
total_value += unit_value[i] * remaining_capacity;
break;
}
}

return total_value;
}

int main() {
int n = 3;
double weights[] = {10, 20, 30};
double values[] = {60, 100, 120};
double capacity = 50;

double max_value = knapsack(weights, values, n, capacity);
printf("背包能装的最大价值为: %.2f\n", max_value);

return 0;
}

该示例中，我们假设背包容量为50，有3个物品，其重量和价值分别为{10, 20, 30} 和{60, 100, 120}。通过运行程序，可以得到背包能装的最大价值为220。

### 回答3：
贪心算法是一种解决问题的策略，它总是做出当前看来最优的选择，而不考虑整体的最优解。下面我将用300字来介绍贪心算法的一个C语言实现示例。

假设有一批货物，每个货物都有自己的重量和价值，目标是在给定的背包容量下装入尽可能多的货物，并且使得装入的货物总价值最大。

首先，我们需要定义一个结构体来表示每个货物的重量和价值：

typedef struct {
    int weight;
    int value;
} Goods;

接下来，我们定义一个贪心算法函数来实现货物的装载：

int knapsack(Goods* goods, int n, int capacity) {
    // 对货物按单位重量的价值进行排序（从高到低）
    qsort(goods, n, sizeof(Goods), compare);
    
    int totalValue = 0; // 总价值
    int currentWeight = 0; // 当前背包重量
    
    for (int i = 0; i < n; i++) {
        if (currentWeight + goods[i].weight <= capacity) {
            currentWeight += goods[i].weight;
            totalValue += goods[i].value;
        } else {
            break;
        }
    }
    
    return totalValue;
}

在贪心算法函数中，我们首先对货物按单位重量的价值进行排序，调用 `qsort` 函数，并提供一个自定义的比较函数 `compare` 来实现。然后，我们按照货物的排序顺序依次将货物放入背包，直到背包已满为止。

最后，我们可以使用该贪心算法函数来求解具体例子：

Goods goods[] = {
    {10, 60},
    {20, 100},
    {30, 120}
};
int n = sizeof(goods) / sizeof(Goods);
int capacity = 50;

int result = knapsack(goods, n, capacity);
printf("Total value: %d\n", result);

以上是一个简单的贪心算法的C语言实现示例，它通过贪心的方式选择当前最优的货物放入背包，从而求解背包问题的最优解。