背包问题贪心算法c语

背包问题是一个经典的动态规划问题，而贪心算法是一种常用的解决背包问题的方法。下面是一个使用C语言实现的背包问题贪心算法的示例代码：

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

typedef struct {
    int weight; // 物品重量
    int value; // 物品价值
    double rate; // 物品价值率
} Object;

void sort(Object A[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        int a = i;        for (j = i + 1; j < n; j++) {
            if (A[j].rate > A[a].rate) {
                a = j;
            }
        }
        Object temp = A[a];
        A[a] = A[i];
        A[i] = temp;
    }
}

int main() {
    int n, c; // 物品数量和背包容量
    scanf("%d%d", &n, &c);
    Object *objects = (Object *)malloc(n * sizeof(Object));
    int i;
    for (i = 0; i < n; i++) {
        scanf("%d%d", &objects[i].weight, &objects[i].value);
        objects[i].rate = (double)objects[i].value / objects[i].weight;
    }
    sort(objects, n);
    int E = 0, D = 0; // 背包中物品的总价值和总重量
    for (i = 0; i < n; i++) {
        if (objects[i].weight <= c) {
            E += objects[i].value;
            D += objects[i].weight;
            c -= objects[i].weight;
        } else {
            int demo = (objects[i].value / objects[i].weight * 1.0) * c;
            E += demo;
            D += demo * objects[i].weight / objects[i].value * 1.0;
            break;
        }
    }
    printf("背包中物品的总价值为：%d，总重量为：%d\n", E, D);
    free(objects);
    return 0;
}