c语言代码0-1背包问题
时间: 2024-05-07 11:14:17 浏览: 17
0-1背包问题是一类经典的背包问题,在计算机算法中有着广泛的应用。假设有一个固定容量的背包,和一些物品,每个物品有自己的重量和价值,在不超过背包容量的前提下,如何选择物品放入背包,使得背包中物品的总价值最大化,这就是0-1背包问题。
下面是C语言代码实现0-1背包问题,其中w[i]表示第i个物品的重量,v[i]表示第i个物品的价值,W表示背包的容量。
```
#include<stdio.h>
#define MAX_N 1000
#define MAX_W 1000
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N + 1][MAX_W + 1] = {0};
// 输入物品数量n和背包容量W
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++) {
if (j < w[i]) {
dp[i + 1][j] = dp[i][j];
} else {
dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
}
}
}
// 输出最大价值
printf("%d\n", dp[n][W]);
return 0;
}
```