C语言写一段贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。下面是一个使用C语言实现的贪心算法的例子：找零问题。

#include <stdio.h>

// 找零问题：使用最少的硬币数量来凑出指定金额
int minCoins(int coins[], int n, int amount) {
    int count = 0;

    // 从大到小排序硬币
    for (int i = n - 1; i >= 0; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            count++;
        }
    }

    if (amount != 0) {
        return -1; // 无法凑出指定金额
    }

    return count;
}

int main() {
    int coins[] = {1, 5, 10, 25};
    int n = sizeof(coins) / sizeof(coins[0]);
    int amount = 67;

    int result = minCoins(coins, n, amount);

    if (result != -1) {
        printf("最少需要 %d 个硬币\n", result);

相关问题

用C语言写一段贪心算法

### 回答1：
很高兴回答你的问题。以下是一段使用 C 语言编写的贪心算法示例，用于解决背包问题：

#include <stdio.h>

#define MAX_N 100

int n, m;
int w[MAX_N], v[MAX_N];
double f[MAX_N];

int cmp(const void *a, const void *b) {
    double x = *(double *)a, y = *(double *)b;
    if (x < y) return 1;
    if (x > y) return -1;
    return ;
}

double max(double x, double y) {
    return x > y ? x : y;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = ; i < n; i++) {
        scanf("%d%d", &w[i], &v[i]);
        f[i] = (double)v[i] / w[i];
    }
    qsort(f, n, sizeof(double), cmp);
    double ans = ;
    for (int i = ; i < n; i++) {
        if (m >= w[i]) {
            ans += v[i];
            m -= w[i];
        } else {
            ans += m * f[i];
            break;
        }
    }
    printf("%.2lf\n", ans);
    return ;
}

这段代码实现了一个简单的背包问题，其中 `n` 表示物品数量，`m` 表示背包容量，`w[i]` 表示第 `i` 个物品的重量，`v[i]` 表示第 `i` 个物品的价值，`f[i]` 表示第 `i` 个物品的单位价值。我们首先计算每个物品的单位价值，然后按照单位价值从大到小排序，依次将物品放入背包中，直到背包装满或者所有物品都放完为止。

### 回答2：
贪心算法是一种基于贪心的策略，在每一步都选择当前最优解来最终获得全局最优解的方法。在C语言中实现贪心算法，可以通过以下代码片段示例：

#include <stdio.h>

// 定义物品结构体
struct Item {
    int value;  // 物品的价值
    int weight; // 物品的重量
};

// 按照物品的价值-重量比例排序
int compare(const void* a, const void* b) {
    struct Item* itemA = (struct Item*)a;
    struct Item* itemB = (struct Item*)b;
    double ratioA = (double)itemA->value / itemA->weight;
    double ratioB = (double)itemB->value / itemB->weight;
    if (ratioA > ratioB) {
        return -1;
    } else if (ratioA < ratioB) {
        return 1;
    } else {
        return 0;
    }
}

// 贪心算法求解背包问题
double greedyKnapsack(struct Item items[], int n, int capacity) {
    // 按照价值-重量比例排序
    qsort(items, n, sizeof(struct Item), compare);
    
    int currentWeight = 0;  // 当前已装入的物品的总重量
    double currentValue = 0.0;  // 当前已装入的物品的总价值
    
    // 从价值-重量比例最高的物品开始装入背包
    for (int i = 0; i < n; i++) {
        if (currentWeight + items[i].weight <= capacity) {
            currentWeight += items[i].weight;
            currentValue += items[i].value;
        } else {
            // 当前物品无法完整装入背包时，则按照比例装入部分物品
            int remainingWeight = capacity - currentWeight;
            currentValue += (double)items[i].value / items[i].weight * remainingWeight;
            break;
        }
    }
    
    return currentValue;
}

int main() {
    struct Item items[] = {
        {60, 10},
        {100, 20},
        {120, 30}
    };
    int n = sizeof(items) / sizeof(items[0]);
    int capacity = 50;
    
    double maximumValue = greedyKnapsack(items, n, capacity);
    
    printf("背包能装入的最大价值为: %.2lf\n", maximumValue);

    return 0;
}

以上代码展示了一个贪心算法用于解决背包问题的例子。通过贪心策略按照物品的价值-重量比例排序，依次选择更具比例最高的物品装入背包，直到背包无法装入更多物品或者已经装满为止。运行结果将输出背包能装入的最大价值。

### 回答3：
贪心算法是一种常见的算法思想，它在每一步都会选择当前情况下的最优解，希望最终能够得到全局最优解。接下来，我将用300字中文来编写一段用C语言实现的贪心算法的示例：

#include <stdio.h>

void greedy(int coins[], int num, int amount) {
    int count[num];
    for(int i = 0; i < num; i++) {
        count[i] = 0;
    }
    
    for(int i = num - 1; i >= 0; i--) {
        while(amount >= coins[i]) {
            amount -= coins[i];
            count[i]++;
        }
    }
    
    for(int i = num - 1; i >= 0; i--) {
        if(count[i] > 0) {
            printf("%d元硬币：%d个\n", coins[i], count[i]);
        }
    }
}

int main() {
    int coins[] = {10, 5, 2, 1};
    int num = sizeof(coins) / sizeof(coins[0]);
    int amount;
    
    printf("请输入要找零的金额：");
    scanf("%d", &amount);
    
    printf("找零方案如下：\n");
    greedy(coins, num, amount);
    
    return 0;
}

以上代码实现了一个简单的贪心算法，用于找零钱问题。假设现有10元、5元、2元和1元硬币若干枚，要找零n元，该算法会从最大面额的硬币开始逐步减少找零的金额，并计算每种硬币所需的数量。最后，算法将输出找零方案。使用示例中的输入10元，则输出为：

请输入要找零的金额：10
找零方案如下：
10元硬币：1个

这个示例展示了贪心算法的基本思想和具体实现过程。

用c语言写一段贪心算法代码【问题描述】有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i（1≤i≤n）的重量为wi。不考虑集装箱的体积限制，现要选出尽可能多的集装箱装上轮船，使它们的重量之和不超过W。 【测试用例】n=5,各集装箱重量{5,2,6,4,3};W=10;

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

#define MAX_N 10000 // 最大集装箱数量

typedef struct {
int weight; // 集装箱重量
int index; // 集装箱编号（用于记录最终选中的集装箱）
} container;

int cmp(const void *a, const void *b) {
return ((container *)a)->weight - ((container *)b)->weight;
}

int main() {
int n, W;
container c[MAX_N];

// 输入集装箱数量和轮船载重量
scanf("%d%d", &n, &W);

// 输入每个集装箱的重量
for (int i = 0; i < n; i++) {
scanf("%d", &c[i].weight);
c[i].index = i + 1; // 编号从1开始
}

// 按重量从小到大排序
qsort(c, n, sizeof(container), cmp);

int i = 0;
int sum = 0;
while (i < n && sum + c[i].weight <= W) {
sum += c[i].weight;
i++;
}

printf("选中的集装箱编号为：");
for (int j = 0; j < i; j++) {
printf("%d ", c[j].index);
}
printf("\n");

return 0;
}