使用c语言实现上述代码
时间: 2024-02-09 21:08:46 浏览: 29
好的,以下是使用C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, m;
scanf("%d %d", &n, &m); // n是草药的数量,m是背包的容量
int *v = (int*)malloc(sizeof(int) * n); // 存储草药的价值
int *w = (int*)malloc(sizeof(int) * n); // 存储草药的重量
for (int i = 0; i < n; i++) {
scanf("%d %d", &v[i], &w[i]);
}
int **dp = (int**)malloc(sizeof(int*) * (n + 1)); // dp[i][j]表示前i个草药,背包容量为j时的最大价值
for (int i = 0; i <= n; i++) {
dp[i] = (int*)malloc(sizeof(int) * (m + 1));
for (int j = 0; j <= m; j++) {
dp[i][j] = 0; // 初始化为0
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j >= w[i - 1]) { // 如果当前背包容量可以放下第i个草药
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]); // 取放或不放第i个草药的最大值
} else {
dp[i][j] = dp[i - 1][j]; // 否则只能不放第i个草药
}
}
}
printf("%d\n", dp[n][m]); // 输出最大价值
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
free(dp);
free(v);
free(w);
return 0;
}
```
以上代码使用了动态内存分配来创建数组,通过循环来处理状态转移。同样地,我们使用一个二维数组dp来存储状态,其中dp[i][j]表示前i个草药,背包容量为j时的最大价值。在每次迭代中,我们判断当前背包容量是否可以放下第i个草药,如果可以,则取放或不放第i个草药的最大值,否则只能不放第i个草药。最后输出dp[n][m]即可得到最大价值。注意,使用完动态分配的内存后,需要及时释放,以防止内存泄漏。