假设有一个背包能承受最大重量为M,有n个物品,每个物品有自己的重量和价值。首先按照价值与重量的比值对物品进行排序,然后按照这个比值从大到小依次选择物品放入背包,直到背包不能再装下更多物品为止。 用贪心算法C代码
时间: 2024-10-10 22:16:42 浏览: 10
这是一个经典的0-1背包问题(Knapsack problem),可以使用贪心策略解决。以下是使用C语言的一个简单实现,假设物品结构为`struct Item`,包含`weight`(重量)和`value`(价值)两个字段:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int weight;
int value;
} Item;
// 比较物品价值与重量的比值,用于排序
int compare(const void* a, const void* b) {
const Item* item_a = (const Item*)a;
const Item* item_b = (const Item*)b;
return item_b->value * 1.0 / item_b->weight - item_a->value * 1.0 / item_a->weight;
}
// 贪心求解0-1背包问题
int knapSack(int W, Item items[], int n) {
// 对物品按价值密度排序
qsort(items, n, sizeof(Item), compare);
int total_value = 0; // 最大总价值
for (int i = 0; i < n && items[i].weight <= W; i++) {
if (W >= items[i].weight)
W -= items[i].weight;
else // 如果剩余容量不足以放下整件物品,就只拿走部分
W = 0;
total_value += items[i].value;
}
return total_value;
}
int main() {
int M = 50; // 包的承重限制
int n = 6; // 物品数量
Item items[] = { {10, 60}, {20, 100}, {30, 120}, {40, 140}, {50, 160}, {60, 180} }; // 示例物品
printf("最大价值: %d\n", knapSack(M, items, n));
return 0;
}
```
阅读全文