用c++写一个贪心程序
时间: 2023-05-20 18:01:50 浏览: 52
好的,以下是一个简单的贪心程序示例,用于解决背包问题:
```c
#include <stdio.h>
#define MAX_N 1000
struct Item {
int weight;
int value;
};
int cmp(const void *a, const void *b) {
const struct Item *ia = (const struct Item *)a;
const struct Item *ib = (const struct Item *)b;
return (ib->value / ib->weight) - (ia->value / ia->weight);
}
int main() {
int n, w;
struct Item items[MAX_N];
printf("请输入物品数量和背包容量:\n");
scanf("%d %d", &n, &w);
printf("请输入每个物品的重量和价值:\n");
for (int i = 0; i < n; i++) {
scanf("%d %d", &items[i].weight, &items[i].value);
}
qsort(items, n, sizeof(struct Item), cmp);
int ans = 0;
for (int i = 0; i < n; i++) {
if (w >= items[i].weight) {
ans += items[i].value;
w -= items[i].weight;
} else {
ans += w * (items[i].value / items[i].weight);
break;
}
}
printf("最大价值为:%d\n", ans);
return 0;
}
```
这个程序使用了贪心算法来解决背包问题,它首先按照每个物品的单位价值(即价值除以重量)从大到小排序,然后依次将物品放入背包中,直到背包装满为止。如果某个物品不能完全放入背包中,则只放入一部分。