贪心算法求解背包问题C语言
时间: 2023-07-07 19:08:47 浏览: 48
下面是一个简单的贪心算法求解背包问题的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int weight;
int value;
double ratio;
} Item;
int compare(const void * a, const void * b) {
Item *itemA = (Item *)a;
Item *itemB = (Item *)b;
return (int)(itemB->ratio - itemA->ratio);
}
double knapsack(Item *items, int n, int capacity) {
qsort(items, n, sizeof(Item), compare);
double totalValue = 0.0;
for (int i = 0; i < n; i++) {
if (capacity >= items[i].weight) {
capacity -= items[i].weight;
totalValue += items[i].value;
} else {
totalValue += items[i].ratio * capacity;
break;
}
}
return totalValue;
}
int main() {
Item items[] = {{10, 60}, {20, 100}, {30, 120}};
int n = sizeof(items) / sizeof(Item);
int capacity = 50;
double result = knapsack(items, n, capacity);
printf("The maximum value we can obtain is %.2f\n", result);
return 0;
}
```
首先定义了一个`Item`结构体,表示物品的重量和价值,以及它们的价值重量比。然后定义了一个比较函数`compare`,用于按照价值重量比从大到小排序。接着实现了`knapsack`函数,它首先按照价值重量比对物品进行排序,然后遍历每个物品,如果当前物品可以放入背包,则将它的价值加入总价值中,并减去背包容量;否则,将该物品的部分价值按比例加入总价值中,然后跳出循环。最后,在`main`函数中定义了一些测试数据,并调用`knapsack`函数来求解最大价值。