用C语言编写1.给定N种物品和一个背包。物品i的重量是w[i],其价值为v[i],背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 2.在选择装入背包的物品时,对每种物品i只有2种选择:装入背包(=1)或不装入背包(=0)。不能将物品i装入背包多次,在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包。第一行输入两个整数0<N<=1000,0<C<108,N表示物品的数量,C表示背包的容量。 接下来N行,每行读入两个实数Wi,Vi,分别表示物品i的重量和其价值。输出N行,每行输出 "物品编号: 装入程度",按物品单位重量的价值降序输出。
时间: 2023-12-02 19:23:47 浏览: 38
以下是完整的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
int N, C;
int w[MAXN+1], v[MAXN+1];
int f[MAXN+1][1000001], g[MAXN+1][1000001];
int cmp(const void* a, const void* b) {
double c = ((double*)b)[2] / ((double*)b)[1];
double d = ((double*)a)[2] / ((double*)a)[1];
if (c > d) return 1;
if (c < d) return -1;
return 0;
}
int main() {
scanf("%d%d", &N, &C);
for (int i = 1; i <= N; i++) {
scanf("%d%d", &w[i], &v[i]);
}
qsort(w+1, N, sizeof(int), cmp);
qsort(v+1, N, sizeof(int), cmp);
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= C; j++) {
f[i][j] = f[i-1][j];
g[i][j] = 0;
if (j >= w[i] && f[i][j] < f[i-1][j-w[i]]+v[i]) {
f[i][j] = f[i-1][j-w[i]]+v[i];
g[i][j] = 1;
}
}
}
for (int i = 1; i <= N; i++) {
double res = 0;
if (g[i][C]) {
res = 1;
C -= w[i];
} else if (C > 0) {
res = (double)C / w[i];
C = 0;
}
printf("物品%d: %.2f\n", i, res);
}
return 0;
}
```
代码思路如下:
1. 先将物品按单位重量的价值降序排列,这样可以让后面的物品先被考虑。
2. 使用动态规划求解,在每个状态中记录下是否将当前物品放入背包中。
3. 最后根据记录的状态,输出每个物品的装入情况,按照物品单位重量的价值降序输出。
需要注意的是,由于输入的物品数量和背包容量可能非常大,我们需要使用动态数组来存储状态。此外,为了保证输出结果的精度,可以将物品重量和价值用双精度浮点数来存储。