李明做作业贪心算法C语言代码实现

以下是一个简单的贪心算法的C语言代码实现：

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

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

// 比较函数，按照物品的价值重量比从大到小排序
int cmp(const void *a, const void *b) {
    double ratioA = ((struct Item *) a)->value / (double) ((struct Item *) a)->weight;
    double ratioB = ((struct Item *) b)->value / (double) ((struct Item *) b)->weight;
    if (ratioA > ratioB) {
        return -1;
    } else if (ratioA < ratioB) {
        return 1;
    } else {
        return 0;
    }
}

// 贪心算法
double knapsack(int W, struct Item arr[], int n) {
    // 按照物品的价值重量比从大到小排序
    qsort(arr, n, sizeof(struct Item), cmp);

    int i;
    double result = 0.0;
    int currentWeight = 0;

    for (i = 0; i < n; i++) {
        // 如果当前物品能全部装入背包
        if (currentWeight + arr[i].weight <= W) {
            currentWeight += arr[i].weight;
            result += arr[i].value;
        } else {
            // 否则，装入部分物品
            int remainWeight = W - currentWeight;
            result += arr[i].value * ((double) remainWeight / arr[i].weight);
            break;
        }
    }

    return result;
}

int main() {
    int W = 50; // 背包容量
    struct Item arr[] = {{60, 10}, {100, 20}, {120, 30}}; // 物品数组
    int n = sizeof(arr) / sizeof(arr[0]); // 物品数量

    double max_value = knapsack(W, arr, n);

    printf("The maximum value of items that can be put into knapsack is: %f\n",
           max_value);

    return 0;
}

上述代码实现的是一个简单的背包问题，使用了贪心算法。具体来说，它按照物品的价值重量比从大到小排序，然后依次将物品放入背包中，直到背包装满为止。如果当前物品不能全部放入背包，就将一部分物品放入背包，然后退出循环。最终，程序输出能够放入背包的物品的最大价值。