贪心算法背包问题c语言实现

好的，以下是贪心算法背包问题的C语言实现：

#include <stdio.h>

#define MAX_N 100

int n, W; // 物品数量，背包容量
int w[MAX_N], v[MAX_N]; // 物品重量，物品价值

typedef struct {
int id; // 物品编号
double density; // 单位重量价值
} Item;

int cmp(const void *a, const void *b) {
Item *itemA = (Item *) a;
Item *itemB = (Item *) b;
if (itemA->density < itemB->density) {
return 1; // 按照单位重量价值从高到低排序
} else if (itemA->density > itemB->density) {
return -1;
} else {
return 0;
}
}

int main() {
scanf("%d %d", &n, &W);
for (int i = 0; i < n; i++) {
scanf("%d %d", &w[i], &v[i]);
}
Item items[n];
for (int i = 0; i < n; i++) {
items[i].id = i;
items[i].density = (double) v[i] / w[i]; // 计算单位重量价值
}
qsort(items, n, sizeof(Item), cmp); // 排序
int i = 0;
double ans = 0;
while (W > 0 && i < n) { // 只要还有空余容量且还有物品可选
int j = items[i].id;
int k = W >= w[j] ? w[j] : W; // 选择一部分或全部装入背包
ans += k * items[i].density;
W -= k;
i++;
}
printf("%.2lf\n", ans);
return 0;
}

希望能够帮助到你。