有一个背包的容量为C,有n个物品，每个物品的重量为w1,w2,...wn,每个物品的价值为v1,v2,v3...vn,装入哪些物品使背包中的物品价值最大。通过键盘输入背包的容量，物品的个数以及每个物品的重量和价值，使用贪心算法求出装入背包的中的物品价值的最大值。C语言

实现如下：

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

typedef struct {
int w; // 物品重量
int v; // 物品价值
double r; // 物品单位价值
} Item;

int cmp(const void *a, const void *b) {
Item *ia = (Item *)a;
Item *ib = (Item *)b;
return (int)(ib->r - ia->r);
}

int main() {
int c, n;
printf("请输入背包容量和物品个数：");
scanf("%d%d", &c, &n);
Item *items = (Item *)malloc(sizeof(Item) * n);
printf("请输入每个物品的重量和价值：\n");
for (int i = 0; i < n; i++) {
scanf("%d%d", &items[i].w, &items[i].v);
items[i].r = (double)items[i].v / items[i].w;
}
qsort(items, n, sizeof(Item), cmp);
int max_v = 0; // 背包中的物品价值最大值
int cur_w = 0; // 当前已装入背包的物品重量
for (int i = 0; i < n && cur_w < c; i++) {
int w = items[i].w;
int v = items[i].v;
if (cur_w + w <= c) {
max_v += v;
cur_w += w;
} else {
max_v += (c - cur_w) * items[i].r;
break;
}
}
printf("背包中的物品价值最大值为：%d\n", max_v);
free(items);
return 0;
}