根据以下要求写一段c语言代码【问题描述】n个商品组成集合O,每个商品有两个属性vi和pi,分别表示体积和价格。背包容量为C,找到其中背包所能装下的最大价格商品 【输入形式】13;10,24;3,2;4,9;5,10;4,9; 【输出形式】28 【样例输入】13;10,24;3,2;4,9;5,10;4,9;
时间: 2024-03-12 16:49:32 浏览: 118
好的,根据你的要求,以下是C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100000
typedef struct {
int v; // 体积
int p; // 价格
} Goods;
int cmp(const void* a, const void* b) {
Goods* g1 = (Goods*) a;
Goods* g2 = (Goods*) b;
double r1 = (double) g1->p / g1->v;
double r2 = (double) g2->p / g2->v;
if (r1 > r2) {
return -1;
} else if (r1 < r2) {
return 1;
} else {
return 0;
}
}
int main() {
int C, n;
scanf("%d;%d", &C, &n);
Goods goods[MAX_N];
for (int i = 0; i < n; i++) {
scanf("%d,%d", &goods[i].v, &goods[i].p);
}
qsort(goods, n, sizeof(Goods), cmp); // 按照单位体积价值降序排序
int ans = 0;
for (int i = 0; i < n; i++) {
if (C - goods[i].v >= 0) {
ans += goods[i].p;
C -= goods[i].v;
} else {
ans += (double) goods[i].p / goods[i].v * C;
break;
}
}
printf("%d\n", ans);
return 0;
}
```
使用了贪心算法来解决背包问题。首先按照单位体积价值(即价格除以体积)降序排序,然后从价值最高的商品开始,依次选取商品放入背包,直到背包已经没有剩余空间或者已经选完了所有的商品。如果当前商品的体积小于等于背包的剩余空间,则将该商品放入背包,否则将该商品的一部分放入背包。最后输出放入背包的商品的总价格。
需要注意的是,输入格式中的分号和逗号需要使用 `%c` 占位符读入,但是不需要保存。排序函数 `qsort` 的第三个参数需要传入结构体的大小。
阅读全文