现有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 。要求保留小数点后两位,第三位按照四舍五入处理。用贪心法C语言解决
时间: 2024-03-07 07:50:28 浏览: 23
使用贪心算法求解 0-1 背包问题的最优解是不可行的,但是对于部分分数背包问题,贪心算法可以给出一个近似最优解。
具体地,我们可以按照物品单位重量价值的降序排序,然后依次考虑每个物品:
- 若当前物品可以完全放入背包,则将其全部放入;
- 否则,将能够放入背包的部分全部放入。
这样做的正确性在于,对于单位重量价值更高的物品,我们优先考虑将其放入背包,而对于不能完全放入背包的物品,我们优先选择其单位重量价值更高的部分放入背包,这样可以保证我们所选择的物品的总价值是一个近似最优解。
以下是 C 语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000
int n, m;
int w[MAX_N], p[MAX_N];
double x[MAX_N];
int cmp(const void *a, const void *b) {
double va = (double)p[*(int *)a] / w[*(int *)a];
double vb = (double)p[*(int *)b] / w[*(int *)b];
if (va > vb) {
return -1;
} else if (va < vb) {
return 1;
} else {
return 0;
}
}
int main() {
scanf("%d %d", &m, &n);
int idx[n];
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
idx[i] = i;
}
for (int i = 0; i < n; i++) {
scanf("%d", &p[i]);
}
qsort(idx, n, sizeof(int), cmp);
double ans = 0;
for (int i = 0; i < n && m > 0; i++) {
int j = idx[i];
if (w[j] <= m) {
x[j] = 1.0;
ans += p[j];
m -= w[j];
} else {
x[j] = (double)m / w[j];
ans += p[j] * x[j];
m = 0;
}
}
printf("%.2f\n", ans);
for (int i = 0; i < n; i++) {
printf("%.2f ", x[i]);
}
printf("\n");
return 0;
}
```
时间复杂度:$O(n\log n)$
空间复杂度:$O(n)$