【程序设计竞赛算法】动态规划——背包问题_绘制一个二维数组,利用动态规划法求解背包问题

【程序设计竞赛算法】动态规划——背包问题

动态规划是解决背包问题的经典方法之一。它通过构建一个二维数组（或者称为状态表）来记录子问题的解，然后根据子问题的解逐步推导出整体问题的解。

背包问题可以分为 0-1 背包问题和分数背包问题。下面分别介绍这两种问题的动态规划解决方法。

1、0-1 背包问题的动态规划解法：

创建一个二维数组 dp，其中 dp[i][j] 表示在前 i 个物品中，背包容量为 j 时的最大总价值。

初始化状态表，将第 0 行和第 0 列都设置为 0。

对于每个物品 i，遍历背包容量 j，根据以下情况更新状态表：

如果物品 i 的重量大于当前背包容量 j，则无法放入背包，即 dp[i][j] = dp[i-1][j]。

如果物品 i 的重量小于等于当前背包容量 j，则可以选择放入背包或者不放入背包，取两者的最大值，即 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，其中 w[i] 是物品 i 的重量，v[i] 是物品 i 的价值。

最终，dp[n][capacity] 即为所求的最大总价值，其中 n 是物品的数量，capacity 是背包的容量。

2、分数背包问题的动态规划解法：

创建一个一维数组 dp，其中 dp[j] 表示背包容量为 j 时的最大总价值。

初始化状态表，将数组 dp 中的所有元素都设置为 0。

对于每个物品 i，遍历背包容量 j，根据以下情况更新状态表：

如果物品 i 的重量大于当前背包容量 j，则无法放入背包，不需要更新 dp[j]。

如果物品 i 的重量小于等于当前背包容量 j，则可以选择放入背包或者不放入背包，取两者的最大值，即 dp[j] = max(dp[j], dp[j-w[i]] + v[i])，其中 w[i] 是物品 i 的重量，v[i] 是物品 i 的价值
。
最终，dp[capacity] 即为所求的最大总价值，其中 capacity 是背包的容量。

下面是使用 C 语言给出一个动态规划解决 0-1 背包问题的具体例子：

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsack(int w[], int v[], int n, int capacity) {
    int dp[n+1][capacity+1];
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (w[i-1] <= j) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    
    return dp[n][capacity];
}

int main() {
    int w[] = {10, 20, 30};
    int v[] = {60, 100, 120};
    int n = sizeof(w) / sizeof(w[0]);
    int capacity = 50;
    
    int result = knapsack(w, v, n, capacity);
    printf("Maximum value: %d\n", result);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

以上代码通过 knapsack 函数计算了给定物品的最大总价值，并在 main 函数中进行了测试。