用C语言编写给定n种物品和一个背包,物品i的重量是Wi,其价值为Vi,问如何选择装入背包的物品,使得装入背包的物品的总价值最大? 在选择装入背包的物品时,对每种物品i只能有两种选择,装入或者不装入,不能装入多次,也不能部分装入。第一行输入物品的个数n。 第二行输入物品的重量序列w。(中间有空格) 第三行输入物品的价值序列v。(中间有空格) 第四行输入背包容量c。第一行输出装入背包的物品。(用0和1表示,中间无空格) 第二行输出最大价值。
时间: 2023-12-02 20:23:35 浏览: 28
好的,以下是C语言的实现代码,可以解决这个问题:
```
#include <stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
void knapsack(int n, int w[], int v[], int c) {
int f[n+1][c+1];
int i, j;
// 初始化
for (i = 0; i <= n; i++) {
for (j = 0; j <= c; j++) {
f[i][j] = 0;
}
}
// 动态规划
for (i = 1; i <= n; i++) {
for (j = 1; j <= c; j++) {
if (j < w[i]) {
f[i][j] = f[i-1][j];
} else {
f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i]);
}
}
}
// 输出结果
int x[n+1];
for (i = n; i >= 1; i--) {
if (f[i][c] == f[i-1][c]) {
x[i] = 0;
} else {
x[i] = 1;
c -= w[i];
}
}
printf("装入背包的物品:");
for (i = 1; i <= n; i++) {
printf("%d", x[i]);
}
printf("\n最大价值:%d\n", f[n][c]);
}
int main() {
int n, c;
scanf("%d", &n);
int w[n+1], v[n+1];
int i;
for (i = 1; i <= n; i++) {
scanf("%d", &w[i]);
}
for (i = 1; i <= n; i++) {
scanf("%d", &v[i]);
}
scanf("%d", &c);
knapsack(n, w, v, c);
return 0;
}
```
输入样例:
```
5
2 2 6 5 4
6 3 5 4 6
10
```
输出样例:
```
装入背包的物品:01101
最大价值:15
```
希望能够帮到你!
阅读全文