用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 。要求保留小数点后两位,第三位按照四舍五入处理。
时间: 2024-02-19 17:03:58 浏览: 90
好的,以下是用C语言贪心算法解决背包问题的代码,并附有注释:
```
#include <stdio.h>
#include <stdlib.h>
#define N 1000 // 最多物品数量
#define MAX(a, b) ((a) > (b) ? (a) : (b)) // 定义求最大值的宏
int n, m; // 物品数量,背包容量
int w[N], p[N]; // 物品重量,物品价值
double x[N], v; // 物品装入背包的量,最大价值之和
// 定义物品结构体
typedef struct {
int w, p, id;
double r; // 价值与重量的比率
} Item;
// 比较函数,按照价值与重量的比率从大到小排序
int cmp(const void *a, const void *b) {
Item *pa = (Item *)a, *pb = (Item *)b;
return pb->r > pa->r ? 1 : -1;
}
int main() {
scanf("%d%d", &m, &n);
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
}
for (int i = 0; i < n; i++) {
scanf("%d", &p[i]);
}
Item items[N];
for (int i = 0; i < n; i++) {
items[i].w = w[i];
items[i].p = p[i];
items[i].id = i;
items[i].r = (double)p[i] / w[i]; // 计算价值与重量的比率
}
qsort(items, n, sizeof(Item), cmp); // 排序
for (int i = 0; i < n; i++) {
// 如果物品i的重量小于背包容量,将物品i装入背包
if (items[i].w <= m) {
x[items[i].id] = 1.0;
m -= items[i].w;
v += items[i].p;
} else {
// 否则将物品i的一部分装入背包
x[items[i].id] = (double)m / items[i].w;
v += x[items[i].id] * items[i].p;
break;
}
}
// 输出结果
printf("%.2lf\n", v);
for (int i = 0; i < n; i++) {
printf("%.2lf ", x[i]);
}
printf("\n");
return 0;
}
```
这个算法的思路是按照价值与重量的比率从大到小排序,然后依次将物品装入背包,直到背包装满为止。如果装不下一个物品,就将这个物品的一部分装入背包。最后输出装入背包物品的总效益为最大的结果。
阅读全文