动态规划法解决0-1背包问题c语言

### 动态规划解决0-1背包问题的C语言实现 以下是基于动态规划方法解决0-1背包问题的一个标准C语言实现。该程序通过二维数组`dp`来存储子问题的结果，从而避免重复计算并提高效率。 #### 实现代码 ```c #include <stdio.h> #include <stdlib.h> void knapsack(int capacity, int n, int *weights, int *values, int **dp) { for (int i = 0; i <= n; i++) { for (int w = 0; w <= capacity; w++) { if (i == 0 || w == 0) { dp[i][w] = 0; } else if (weights[i - 1] <= w) { dp[i][w] = ((values[i - 1] + dp[i - 1][w - weights[i - 1]]) > dp[i - 1][w]) ? (values[i - 1] + dp[i - 1][w - weights[i - 1]]) : dp[i - 1][w]; } else { dp[i][w] = dp[i - 1][w]; } } } } int main() { int capacity = 20; // 背包容量 int n = 5; // 物品数量 int values[] = {60, 100, 120, 70, 80}; // 各物品的价值 int weights[] = {10, 20, 30, 5, 10}; // 各物品的重量 // 初始化DP表 int **dp = (int **)malloc((n + 1) * sizeof(int *)); for (int i = 0; i <= n; i++) { dp[i] = (int *)calloc(capacity + 1, sizeof(int)); } // 计算最优解 knapsack(capacity, n, weights, values, dp); printf("最大价值: %d\n", dp[n][capacity]); // 打印DP表（可选） /* for (int i = 0; i <= n; i++) { for (int j = 0; j <= capacity; j++) { printf("%d ", dp[i][j]); } printf("\n"); } */ // 清理内存 for (int i = 0; i <= n; i++) { free(dp[i]); } free(dp); return 0; } ``` #### 解析 上述代码实现了经典的0-1背包问题解决方案[^1]。 1. `knapsack` 函数用于填充动态规划表格`dp`，其中`dp[i][w]`表示前`i`个物品在总重量不超过`w`的情况下可以获得的最大价值。 2. 如果当前物品可以放入背包，则比较两种情况：不放此物品或放入此物品后的最大价值。 3. 主函数初始化输入数据，并调用`knapsack`完成计算，最后打印出最大价值。 #### 时间与空间复杂度分析 时间复杂度为 \(O(n \times W)\)，其中\(n\)是物品的数量，\(W\)是背包的容量。这是因为我们需要遍历所有的状态组合。 空间复杂度同样为 \(O(n \times W)\)，因为使用了一个二维数组来保存中间结果。如果优化成一维数组，空间复杂度可以降低至 \(O(W)\)[^2]。 --- ###