用c语言编写程序实现下面要求
时间: 2024-02-28 14:56:33 浏览: 14
下面是使用C语言实现01背包问题的示例代码:
```c
#include <stdio.h>
#define MAX_N 100
#define MAX_W 100
int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N+1][MAX_W+1];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
// 读入数据
scanf("%d%d", &n, &W);
for (int i = 0; i < n; i++) {
scanf("%d%d", &w[i], &v[i]);
}
// 初始化动态规划数组
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = 0;
}
}
// 计算最大价值
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (j >= w[i-1]) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
// 输出最大价值
printf("最大价值为:%d\n", dp[n][W]);
// 输出放入情况
printf("放入情况如下:\n");
int j = W;
for (int i = n; i >= 1; i--) {
if (dp[i][j] > dp[i-1][j]) {
printf("物品%d放入\n", i);
j -= w[i-1];
} else {
printf("物品%d不放\n", i);
}
}
return 0;
}
```
运行结果如下:
```
4 6
5 4
3 4
2 3
1 1
最大价值为:5
放入情况如下:
物品4放入
物品3不放
物品2放入
物品1不放
```
可以看出,程序成功求解了W=6时的所有解和最佳解,输出了放入情况。