用c语言实现完整代码:现有n种物品和一个可承载M 重量的背包,n种物品的重量分别为(w 1 , w 2 , …, w n ),n种物品放入背包所获得的效益分别是(p 1 , p 2 , …, p n ) (p i >0),p i 和w i 均是正整数,若将物品i的一部分x i (0<=x i <=1)放入背包,则所获得的效益是p i x i ,问采用怎样的装包方法会使装入背包物品的总效益为最大? 输入格式: 第1行是M和n,表示背包容量为M且有n件物品; 第2行是这n件物品的重量w i ; 第3行是各物品的价值p i 。 输出格式: 第1行是所选物品的最大价值之和; 第2行是各物品装入背包的量x i 。要求保留小数点后两位,第三位按照四舍五入处理。 输入样例1: 20 3 18 15 10 25 24 15 输出样例1: 31.5 0.00 1.00 0.50
时间: 2024-02-19 19:02:53 浏览: 142
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct item {
int weight;
int profit;
double unit_profit;
} Item;
// 比较函数:按照单位重量的价值从大到小排序
int cmp(const void *item1, const void *item2) {
Item *a = (Item *)item1;
Item *b = (Item *)item2;
return b->unit_profit > a->unit_profit;
}
int main() {
int M, n;
scanf("%d %d", &M, &n);
Item items[n];
for (int i = 0; i < n; i++) {
scanf("%d", &items[i].weight);
}
for (int i = 0; i < n; i++) {
scanf("%d", &items[i].profit);
items[i].unit_profit = (double)items[i].profit / items[i].weight;
}
// 按照单位重量的价值从大到小排序
qsort(items, n, sizeof(Item), cmp);
double profit_sum = 0;
double x[n];
for (int i = 0; i < n; i++) {
x[i] = 0;
}
int i = 0;
while (M > 0 && i < n) {
if (items[i].weight <= M) {
x[i] = 1;
M -= items[i].weight;
profit_sum += items[i].profit;
} else {
x[i] = (double)M / items[i].weight;
profit_sum += x[i] * items[i].profit;
M = 0;
}
i++;
}
printf("%.2f", profit_sum);
for (int i = 0; i < n; i++) {
printf(" %.2f", x[i]);
}
printf("\n");
return 0;
}
```
阅读全文