现有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 。要求保留小数点后两位,第三位按照四舍五入处理。用pi/wi实现,用c语言实现,
时间: 2024-02-19 22:03:27 浏览: 55
beibao.rar_M?n
好的,这是一个经典的背包问题,使用动态规划可以解决。以下是你需要的代码,其中包括了注释来帮助你理解每一行的具体含义。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000
#define MAX_M 10000
// 初始化动态规划数组
double dp[MAX_N + 1][MAX_M + 1] = {0};
int main() {
int n, m;
double w[MAX_N + 1];
double p[MAX_N + 1];
double x[MAX_N + 1] = {0}; // 记录每个物品放入的比例
// 读入输入数据
scanf("%d %d", &m, &n);
for (int i = 1; i <= n; i++) {
scanf("%lf", &w[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%lf", &p[i]);
}
// 动态规划求解
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (j < w[i]) { // 背包容量不足,不能装入物品 i
dp[i][j] = dp[i - 1][j];
} else { // 可以装入物品 i,选择装入或不装入物品 i,取最大值
dp[i][j] = fmax(dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]);
}
}
}
// 输出结果
printf("%.2lf\n", dp[n][m]); // 输出最大价值
int j = m;
for (int i = n; i >= 1; i--) {
if (dp[i][j] > dp[i - 1][j]) { // 物品 i 被装入背包
x[i] = 1;
j -= w[i];
} else { // 物品 i 没有被装入背包
x[i] = 0;
}
}
for (int i = 1; i <= n; i++) {
printf("%.2lf ", x[i] * w[i] / p[i]); // 输出每个物品放入的比例
}
printf("\n");
return 0;
}
```
希望这个代码能够帮助到你!
阅读全文