实现0-1背包的动态规划迭代算法c
时间: 2024-05-13 22:16:09 浏览: 50
下面是实现0-1背包的动态规划迭代算法的C语言代码:
```c
#include <stdio.h>
#define MAX_N 1000 // 物品数量最大值
#define MAX_W 1000 // 背包容量最大值
int weight[MAX_N + 1]; // 物品重量数组
int value[MAX_N + 1]; // 物品价值数组
int dp[MAX_N + 1][MAX_W + 1];// 动态规划表
int max(int a, int b) { return a > b ? a : b; }
int main(void) {
int n, w;
scanf("%d%d", &n, &w);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &weight[i], &value[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
if (j < weight[i]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
printf("%d\n", dp[n][w]);
return 0;
}
```
程序首先读入物品数量 `n` 和背包容量 `w`,然后读入每个物品的重量和价值。接下来,程序使用嵌套的循环计算动态规划表 `dp`。最后输出 `dp[n][w]` 即可得到最优解。