动态规划-0-1背包问题

算法动态规划-背包最优解

---

前言

工作四年的我开始重新认识算法，天才第一步，雀氏纸尿裤，算法第一步，API+强大脑回路
聊聊动态规划：
一种很不错的思想：借势，当已经知道（已经算过）前边哪个最好了或者是已经知道前边的结果了直接拿来用，作为后续数据的一个基础，好比spring，不要重复制造轮子

一、动态规划概念描述（想多了解就看看，不想了解直接跳过）

动态规划（Dynamic Programming，简称DP）是一种算法设计技巧，主要用于解决具有重叠子问题和最优子结构特性的问题。它通过将原问题划分为较小的子问题，然后自底向上地解决这些子问题，避免了对重叠子问题的重复计算，从而大幅提高算法效率。

动态规划的核心思想可以概括为以下几个要点：

1. 最优子结构：一个问题的最优解包含其子问题的最优解。这意味着可以通过合并子问题的最优解来构造出全问题的最优解。
2. 重叠子问题：在递归算法中，许多子问题是反复计算的，动态规划算法通过储存这些子问题的解来避免重复计算。
3. 态的定义：动态规划算法中的“状态”通常指问题的某个阶段或者某种状态下的特征，通过定义合适的状态可以有效记录中间结果。
4. 状态转移方程：一旦定义了状态，就需要找到状态之间的转移关系，即状态转移方程。这些方程描述了如何从一个或多个已知状态得出下一个状态的解。
5. 边界条件：确定状态的初始条件，即最简单的子问题的解，用于开始动态规划算法的递推。
6. 备忘录法（Memoization）或表格法（Tabulation）：备忘录法是自顶向下的方法，先解决大问题，必要时递归解决子问题，并将结果存储下来。表格法是自底向上的方法，先计算最基本的子问题，并将其结果存储在表中，然后逐步计算更大问题的解。
7. 补充
   动态规划主要用于解决两类问题：优化问题和计数问题。在优化问题中，动态规划试图找到最小化或最大化某些量的解决方案。在计数问题中，动态规划用来计算有多少种不同方式可以达到某个给定目标。

举个简单的例子：斐波那契序列的计算。一个非常简单的方法是使用递归函数直接根据定义计算，但这样会有很多重叠子问题。使用动态规划，我们可以从计算f(0)和f(1)开始，然后递推计算f(2)，f(3)，直到f(n)。这样每个子问题只计算一次，并且结果可以被缓存重复使用。

总的来说，动态规划是一种有效的用来解决特定类型问题的方法，能够通过减少计算量来提高效率。在开发过程中，合理运用动态规划技巧可以显著提升程序运行的性能，尤其是在处理复杂算法问题时。作为Java开发人员，掌握动态规划对编写高效的算法代码是极其有用的。

二、具体case

问题实例

假设有一个背包容量为5单位，有3件物品，其重量和价值如下：

要求：我们希望选择物品装入背包，以使得背包里的物品总价值最大，但是总重量不超过5。

解题思路：（动态规划分析和解决）

我们会使用一个二维表dp，其中dp[i][j]表示当可选择的物品为前i个，且背包容量为j时，能够装入的最大价值。
（行）对背包承受重量做拆分：当容量为0、1、2、3、4、5
（列）对物品做拆分：物品1、物品2、物品3
具体到每行每列表示的是当前容量下的最大价值是多少

初始条件：

dp[0][j] = 0 （当没有物品可以选择时，无论背包容量如何，能装入的最大价值都是0）
dp[i][0] = 0 （当背包容量为0时，无法装入任何物品，最大价值为0）

填充表格：

我们按照物品一个个的考虑，并且针对不同背包容量情况分别计算可装入的最大价值。

具体过程分析：

i = 1（当有一个物品可以选择时） 按照顺序从物品1到物品3-当前表示物品1

j = 1: 只有容量为1的背包，可以装入物品1，价值6，dp[1][1] = 6。
j = 2: 容量为2的背包也能装下物品1，价值6，dp[1][2] = 6。
j = 3: 容量为3的背包同样能装下物品1，价值6，dp[1][3] = 6。
j = 4: 容量为4的背包装下物品1，价值6，dp[1][4] = 6。
j = 5: 最后对于容量为5的背包，装下物品1，价值6，dp[1][5] = 6。

i = 2（考虑前两个物品）-当前表示物品1和2

j = 1: 只能装下物品1，dp[2][1] = 6。
j = 2: 可以选择只装物品2（价值10），或者只装物品1（价值6），显然我们选择物品2，dp[2][2] = 10。
j = 3:此时可以装下物品2（价值10），或者装下物品1加上dp[1][2]（即前1件物品中装入容量为2的背包的最大价值，而此时只能装物品1，价值6），显然我们选择物品2，dp[2][3] = 10。
j = 4: 可以装下物品2且剩余空间放物品1，则总价值是物品2的价值加上dp[1][2]（为容量为2的背包装入物品1的最大价值），因此dp[2][4] = 10 + 6 = 16。
j = 5: 同上，物品2的价值加上dp[1][3]（装入物品1后剩余背包容量为3的最大价值），dp[2][5] = 10 + 6 = 16。

i = 3（考虑全部物品）

j = 1~2的情况与上面相同，因为物品3的重量为3，超过了背包容量。
j = 3: 可以装下物品3（价值12），或者按照上一个物品的选择，即dp[2][3] = 10，此时应选择物品3，dp[3][3] =12。
j = 4: 可以混合装入物品3和物品1，总价值是物品3的价值加上dp[2][1]（为容量为1的背包装前2件物品的最大价值，此时只能装物品1），因此dp[3][4]> = 12 + 6 = 18。
j = 5:那就是 思考一下？

上代码

要使用Java代码实现背包问题的动态规划解法，我们需要构建一个二维数组dp，其中dp[i][j]表示考虑到第i个物品（1表示物品1，2表示物品2，以此类推），在不超过重量j的前提下能够得到的最大价值。下面是实现0-1背包问题的动态规划解法的Java代码，它将表明如何一步步构建这个数组，并找到最优解。

public class Knapsack {

    public static void main(String[] args) {
        int[] weights = new int[]{1, 2, 3}; // 物品的重量
        int[] values = new int[]{6, 10, 12}; // 物品的价值
        int capacity = 5; // 背包的容量

        int maxValue = knapsack(weights, values, capacity);
        System.out.println("最大总价值为: " + maxValue);
    }

    // 动态规划解决背包问题
    public static int knapsack(int[] weights, int[] values, int capacity) {
        // 物品数量
        int N = weights.length;

        // dp[i][j] 表示考虑前i个物品，在容量不超过j的情况下的最大价值
        int[][] dp = new int[N + 1][capacity + 1];

        // 初始化dp数组（Java中数组已经初始化为0）

        // 构造动态规划表
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= capacity; j++) {
                // 如果当前物品重量超过背包容量，不装入物品i
                if (weights[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 考虑装入或不装入物品i，取可得到的最大价值   核心代码用心理解下边这行
                    dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
                }
            }
        }

        // 动态规划表的最后一个格子即为最大价值
        return dp[N][capacity];
    }
}

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
36
37
38
39

是不是还是没明白？-这就对了，我当时花了三天都没弄明白

结合下边的case分析一下：

分析：dp[3][4]

我们现在要分析的是在表格中填入物品3和容量4时的情况，即计算dp[3][4]的值。这是我们的动态规划表格初始状态：

     | 0 | 1 | 2 | 3 | 4 | 5 |
--------------------------------
物品1| 0 | 6 | 6 | 6 | 6 | 6 |
物品2| 0 | 6 |10 |16 |16 |16 |
物品3| 0 |   |   |   |   |   |

1
2
3
4
5
6

当我们计算dp[3][4]时，我们在决定是否需要把当前考虑的物品3（重量为3，价值为12）放入到背包中。
按照上面的代码行：

dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
我们将3和4代入i和j对应的位置，得到：
dp[3][4] = Math.max(dp[2][4], values[2] + dp[2][4 - weights[2]]);
1
2
3

计算这两个部分：
dp[2][4] 代表题目中第二件物品考虑完毕后，背包容量为4时的最大价值。查看表格可知为16。
values[2] + dp[2][4 - weights[2]]：
values[2] 是第三件物品的价值，即12。
weights[2] 是第三件物品的重量，即3。
4 - weights[2] 就是从当前考虑的背包容量中减去第三件物品的重量，即4 - 3 = 1。
dp[2][1]代表在不考虑第三件物品的情况下，背包容量为1时已经计算出的最大价值。查看表格可知为6。
我们计算得到12 + dp[2][1]即12 + 6 = 18。

最后的选择就是取两者中的较大值：

dp[3][4] = Math.max(16, 18);
1

因此得到：
dp[3][4] = 18。
这意味着对于背包容量为4时，考虑前三件物品的情况下，最大价值是18，而不是16。最优解是选择"物品3"和"物品1"组合以达到价值18。此时表格的第三行第4列（物品3 列4）会被填入18，而不是12。

最终动态规划表更新如下所示：

     | 0 | 1 | 2 | 3 | 4 | 5 |
--------------------------------
物品1| 0 | 6 | 6 | 6 | 6 | 6 |
物品2| 0 | 6 |10 |16 |16 |16 |
物品3| 0 | 6 |10 |12 |18 |   |
1
2
3
4
5

继续这个过程，我们会填满整个表，而dp[N][W]将会给出背包的最大价值，这里N是物品数量，W是背包容量。填满表格后可回溯解，找出哪些物品被放入了背包中。

那么这次你能分析dp[3][5]了吧

总结：

代码实现和理论分析还是存爱差别的，这里依旧是思想先行，代码不明白就直接粘到idea中进行debug调试，将数据都展示出来，走过几次也能明白
还是那句话：路虽远，行则将至，事虽难，作则必成