用C语言有n个物体,第i个物体的重量为wi(wi为正整数)。选择尽量多的物体,使得总重量不超过C。
时间: 2023-11-12 18:29:08 浏览: 29
这是一个经典的背包问题,可以使用动态规划算法来解决。
我们可以定义一个二维数组dp,其中dp[i][j]表示前i个物体中选取重量不超过j的最大价值。
初始化时,当j为0时,dp[i][0]均为0,当i为0时,dp[0][j]均为0。
然后,我们可以使用以下递推式来更新dp数组:
1. 如果j < w[i],则dp[i][j] = dp[i-1][j](当前背包容量装不下第i个物品,只能选择不装第i个物品,和前i-1个物品的最优解相同);
2. 如果j >= w[i],则dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])(当前背包容量可以装下第i个物品,比较选择装第i个物品和不装第i个物品两种情况的价值,选择最大的价值)。
最终,dp[n][C]就是选取的物品的最大价值。
代码如下:
```c
int knapsack(int n, int C, int w[], int v[]) {
int dp[n+1][C+1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= C; j++) {
if (j < w[i]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
}
}
}
return dp[n][C];
}
```
阅读全文