用C语言写一个贪心算法
时间: 2023-12-29 16:53:37 浏览: 30
以下是一个简单的使用贪心算法解决背包问题的C语言代码:
```c
#include <stdio.h>
// 物品结构体
struct item {
int value; // 价值
int weight; // 重量
};
// 按照价值密度从大到小排序
int cmp(const void* a, const void* b) {
struct item* x = (struct item*)a;
struct item* y = (struct item*)b;
double r1 = (double)x->value / x->weight;
double r2 = (double)y->value / y->weight;
if (r1 < r2)
return 1;
else if (r1 > r2)
return -1;
else
return 0;
}
// 使用贪心算法求解背包问题
double knapsack(struct item* items, int n, int capacity) {
int i;
double total_value = 0.0;
qsort(items, n, sizeof(struct item), cmp); // 按照价值密度排序
for (i = 0; i < n; i++) {
if (items[i].weight <= capacity) { // 如果物品可以完全装入背包
total_value += items[i].value;
capacity -= items[i].weight;
} else { // 如果物品不能完全装入背包
total_value += (double)items[i].value / items[i].weight * capacity;
break;
}
}
return total_value;
}
int main() {
struct item items[] = {{60, 10}, {100, 20}, {120, 30}};
int n = sizeof(items) / sizeof(struct item);
int capacity = 50;
double result = knapsack(items, n, capacity);
printf("Total value: %.2f\n", result);
return 0;
}
```
以上代码使用了一个结构体来表示物品,其中包含了物品的价值和重量。在贪心算法中,我们首先按照物品的价值密度(即单位重量的价值)从大到小排序,然后依次将物品装入背包中,直到背包无法再装入任何物品为止。如果当前物品可以完全装入背包中,则将其完全装入;否则只装入部分,使得背包恰好装满。最终返回背包中物品的总价值。