01背包问题c语言代码
时间: 2023-07-31 20:10:01 浏览: 54
以下是01背包问题的动态规划代码实现,以C语言为例:
```c
#include <stdio.h>
#include <stdlib.h>
int knapsack_01(int n, int C, int w[], int v[]) {
// 定义一个二维数组用于保存状态
int **dp = (int **)malloc((n+1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = (int *)malloc((C+1) * sizeof(int));
}
// 初始化状态
for (int j = 0; j <= C; j++) {
dp[0][j] = 0;
}
// 状态转移
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= C; j++) {
if (j >= w[i-1]) {
dp[i][j] = (dp[i-1][j] > dp[i-1][j-w[i-1]]+v[i-1]) ? dp[i-1][j] : dp[i-1][j-w[i-1]]+v[i-1];
} else {
dp[i][j] = dp[i-1][j];
}
}
}
// 返回最终状态
int res = dp[n][C];
// 释放动态分配的内存
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
free(dp);
return res;
}
int main() {
int n = 5;
int C = 10;
int w[] = {2, 2, 6, 5, 4};
int v[] = {6, 3, 5, 4, 6};
int res = knapsack_01(n, C, w, v);
printf("The maximum value is %d.\n", res);
return 0;
}
```
其中,n表示物品数量,C表示背包容量,w和v分别表示物品的重量和价值。在代码中,我们首先动态分配一个n+1行、C+1列的二维数组dp,用于保存状态。然后,我们初始化第0行的状态为0,表示在前0个物品中选择若干个物品放入容量为j的背包中所能获得的最大价值为0。接下来,我们利用状态转移方程,计算出dp[i][j]的值,最后返回dp[n][C],即在前n个物品中选择若干个物品放入容量为C的背包中所能获得的最大价值。最后,我们释放动态分配的内存。
阅读全文