有一个背包的容量为C,有n个物品,每个物品的重量为w1,w2,...wn,每个物品的价值为v1,v2,v3...vn,装入哪些物品使背包中的物品价值最大。通过键盘输入背包的容量,物品的个数以及每个物品的重量和价值,使用贪心算法求出装入背包的中的物品价值的最大值。c语言
时间: 2023-12-02 14:20:44 浏览: 23
实现如下:
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int weight; // 物品重量
int value; // 物品价值
double ratio; // 物品价值与重量的比值
} Item;
int cmp(const void *a, const void *b) {
Item *item1 = (Item *)a;
Item *item2 = (Item *)b;
return item2->ratio - item1->ratio > 0 ? 1 : -1; // 按照价值与重量比值从大到小排序
}
int main() {
int capacity, n;
printf("请输入背包容量:");
scanf("%d", &capacity);
printf("请输入物品个数:");
scanf("%d", &n);
Item items[n];
for (int i = 0; i < n; i++) {
printf("请输入第%d个物品的重量和价值:", i + 1);
scanf("%d %d", &items[i].weight, &items[i].value);
items[i].ratio = (double)items[i].value / items[i].weight;
}
qsort(items, n, sizeof(Item), cmp); // 对物品排序
int max_value = 0;
for (int i = 0; i < n && capacity > 0; i++) {
if (capacity >= items[i].weight) { // 可以全部装下
max_value += items[i].value;
capacity -= items[i].weight;
} else { // 只能部分装下
max_value += capacity * items[i].ratio;
capacity = 0;
}
}
printf("背包中物品的最大价值为:%d\n", max_value);
return 0;
}