背包问题采用贪心算法C语言代码
时间: 2023-07-07 13:11:56 浏览: 37
好的,下面是使用贪心算法实现0-1背包问题的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int w; // 物品重量
int v; // 物品价值
double d; // 单位价值
} Item;
int cmp(const void *a, const void *b) {
Item *x = (Item *)a;
Item *y = (Item *)b;
return y->d > x->d; // 按照单位价值从大到小排序
}
int main() {
int n, c;
scanf("%d %d", &n, &c);
// 定义物品数组和总价值
Item *items = (Item *)malloc(sizeof(Item) * n);
int value = 0;
// 输入物品信息
for (int i = 0; i < n; i++) {
scanf("%d %d", &items[i].w, &items[i].v);
items[i].d = (double)items[i].v / items[i].w; // 计算单位价值
}
// 按照单位价值排序
qsort(items, n, sizeof(Item), cmp);
// 贪心选择
for (int i = 0; i < n; i++) {
if (c >= items[i].w) {
value += items[i].v;
c -= items[i].w;
} else {
value += c * items[i].d;
break;
}
}
// 输出结果
printf("%d\n", value);
// 释放内存
free(items);
return 0;
}
```
这里使用了结构体来表示物品,其中d字段表示单位价值。在输入物品信息后,对物品按照单位价值进行排序,然后按照贪心策略依次选择物品放入背包中,直到背包装满或者所有物品都被选择完毕。注意,在选择物品时,如果当前物品的重量大于背包剩余容量,需要按照贪心策略选择部分物品,而不是完全选择该物品。