背包算法c语言
时间: 2023-07-26 14:12:53 浏览: 42
背包算法是一种动态规划算法,用于解决0/1背包问题。以下是使用C语言实现0/1背包问题的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000
#define MAX_W 1000
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++) {
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;
}
```
在上述代码中,`n`表示物品的数量,`W`表示背包的容量。`w[i]`和`v[i]`分别表示第`i`个物品的重量和价值。`dp[i + 1][j]`表示将前`i`个物品装入容量为`j`的背包中所能获得的最大价值。
在计算`dp[i + 1][j]`时,如果第`i`个物品的重量大于当前背包容量`j`,则无法将该物品装入背包,因此`dp[i + 1][j]`等于`dp[i][j]`;否则,可以选择将该物品装入背包或不装入背包,取两种情况中的最大值。最终的结果为`dp[n][W]`,即将前`n`个物品装入容量为`W`的背包中所能获得的最大价值。
以上就是使用C语言实现背包算法的示例代码。