用C语言解决0/1背包客问题:有n个重量分别为{w1,w2,…,wn}的物品,它们的价值分别为{v1,v2,…,vn},给定一个容量为W的背包。使得背包中物品在必选某些物品的情况下价值最大。
时间: 2023-06-08 17:07:14 浏览: 146
0-1背包问题,选择合适的物品时背包中价值最大
4星 · 用户满意度95%
好的,这是一个经典的背包问题,可以用动态规划算法来解决。
首先我们定义一个二维数组dp[i][j],表示在前i个物品中选取若干个放入容量为j的背包中所能获得的最大价值。则对于每个物品i,有两种情况:
1. 不选物品i,则所能获得的最大价值为dp[i-1][j];
2. 选物品i,则所能获得的最大价值为dp[i-1][j-wi]+vi。
因此状态转移方程为:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi]+vi)
最后,最优解为dp[n][W]。
以下是C语言的代码实现:
```
#include <stdio.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
int main() {
int n, W;
scanf("%d%d", &n, &W);
int w[n+1], v[n+1];
for (int i = 1; i <= n; i++) {
scanf("%d%d", &w[i], &v[i]);
}
int dp[n+1][W+1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= W; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (j >= w[i]) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
printf("%d\n", dp[n][W]);
return 0;
}
```
阅读全文