动态规划法0-1背包问题c语言
时间: 2023-09-05 16:13:13 浏览: 50
下面是使用动态规划法解决 0-1 背包问题的 C 语言代码。其中,items[] 数组存储物品的重量和价值,weight[] 和 value[] 数组分别存储背包容量和价值。
```c
#include <stdio.h>
#define MAX_WEIGHT 100 // 背包最大容量
#define MAX_ITEMS 100 // 物品最大数量
int weight[MAX_ITEMS+1]; // 物品重量
int value[MAX_ITEMS+1]; // 物品价值
int dp[MAX_ITEMS+1][MAX_WEIGHT+1]; // 动态规划数组
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n; // 物品数量
int w; // 背包容量
printf("请输入物品数量和背包容量:");
scanf("%d%d", &n, &w);
printf("请输入每个物品的重量和价值:\n");
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;
}
```
在上面的代码中,使用二维数组 dp[i][j] 存储前 i 个物品,容量为 j 时的最大价值。在动态规划过程中,如果当前物品的重量大于当前背包容量,那么最大价值就是前 i-1 个物品,容量为 j 时的最大价值。否则,最大价值就是前 i-1 个物品,容量为 j 时的最大价值和前 i-1 个物品,容量为 j-weight[i] 时的最大价值加上当前物品的价值中的较大值。最终,dp[n][w] 就是最大价值。