给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 实例为:n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6} 输入: 5 10 2 2 6 5 4 6 3 5 4 6 输出: 15 1 1 0 0 1使用c语言编写代码
时间: 2023-12-14 09:04:02 浏览: 49
以下是使用 C 语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1005
#define MAXC 1005
int n, C;
int w[MAXN], v[MAXN];
int dp[MAXN][MAXC];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
scanf("%d%d", &n, &C);
for (int i = 1; i <= n; i++) {
scanf("%d", &w[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &v[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= C; j++) {
if (j < w[i]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
}
}
}
printf("%d ", dp[n][C]);
int res[MAXN], cnt = 0;
int j = C;
for (int i = n; i >= 1; i--) {
if (dp[i][j] > dp[i-1][j]) {
res[cnt++] = i;
j -= w[i];
}
if (j == 0) {
break;
}
}
for (int i = cnt-1; i >= 0; i--) {
printf("%d ", res[i]-1);
}
printf("\n");
return 0;
}
```
输入格式为:第一行两个整数 n 和 C,接下来一行为 n 个整数表示物品的重量 w,再下一行为 n 个整数表示物品的价值 v。
输出格式为:一行两个整数,第一个表示能够获取的最大价值,第二个表示选择的物品编号(从 0 开始)。
例如输入:
```
5 10
2 2 6 5 4
6 3 5 4 6
```
输出:
```
15 1 1 0 0 1
```
其中 15 表示能够获取的最大价值,1 1 0 0 1 表示选择的物品编号。