动态规划详解：0-1背包与完全背包问题

动态规划详解：0-1背包与完全背包问题

动态规划是一种通过将问题分解为更小的子问题来求解复杂问题的算法策略。在动态规划中，背包问题是一个经典的优化问题，它可以分为0-1背包问题和完全背包问题两种类型。本文将详细讲解这两种背包问题的解法及其在实际问题中的应用。

什么是背包问题？

背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkle和Hellman提出的。

动态规划问题的一般解决办法：

动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤:

• 步骤一:定义dp数组元素的含义
• 步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)
• 第三步骤：找出初始值（base case）

接下来的题目我们会按照这三个步骤来解释说明

前言：本文包含动态规划中的经典背包问题，有关背包问题的描述如下：

在动态规划中，背包问题是一个经典的优化问题，它可以分为0-1背包问题和完全背包问题两种类型。下面我们就来看看这两个问题：

0-1背包问题：

问题描述：

给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]。现在让你用这个背包装物品，每个物品只能用一次，在不超过被包容量的前提下，最多能装的价值是多少？

• 步骤一:定义dp数组元素的含义：

由于状态有两个，就是「背包的容量」和「可选择的物品」，这里我们就需要用到一个二维的dp数组，如下为dp数组的定义：

dp[i][w]的定义如下：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]

• 步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)

1.如果你没有把这第i个物品装入背包，那么很显然，最大价值dp[i][w]应该等于dp[i-1][w]，继承之前的结果(翻译一下就是不装入第i个物品，相当于对前 i - 1 个物品进行选择，对应此时的背包容量w)。即此时的状态转移方程是：dp[ i ][ w ] = dp[ i - 1 ][ w ]

2.如果你把这第i个物品装入了背包,此时背包剩余容量为 w - wt[ i - 1 ](wt数组下标是从0开始的, wt[ i - 1 ] 相当于第 i 个物品的重量，val 也一样)

则此时的状态转移方程是：dp[ i ][ w ] = dp[ i - 1 ][ w - wt[ i - 1] ] + val[ i - 1 ]

• 第三步骤：找出初始值（base case）：

这题的base case 相对简单，当物品个数为0或则背包当前容量为0时，dp[ i ][ w ] 都等于0

按照上述的状态转移方程，我们可以填出对应dp表格（以图中的例子为例）：

有了上述铺垫后，动态规划的代码就很好实现了，具体代码如下：

int knapsack(int W, int N, int[] wt, int[] val) {
    assert N == wt.length;
    // base case 已初始化，数组自动全部初始化为0
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                // 这种情况下只能选择不装入背包
                dp[i][w] = dp[i - 1][w];
            } else {
                // 装入或者不装入背包，择优
                dp[i][w] = Math.max(
                    dp[i - 1][w - wt[i-1]] + val[i-1],
                    dp[i - 1][w]
                );
            }
        }
    }
    return dp[N][W];
}

有了上面的一定了解后，我们来看看0 - 1背包的类似题：

0 - 1背包类问题 分割等和子集：

看一下力扣第 416 题「分割等和子集」：

题目描述：输入一个只包含正整数的非空数组nums，请你写一个算法，判断这个数组是否可以被分割成两个子集，使得两个子集的元素和相等。对应函数签名如下：

我们可以将这个问题转化为0 - 1背包问题，具体做法：

这个问题相当于给一个可装载重量为sum / 2的背包和N个物品，每个物品的重量为nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？按照上述解题思路就是：

• 步骤一:定义dp数组元素的含义：

dp[i][j] = x 表示，对于前i个物品（i从 1 开始计数），当前背包的容量为j时，若x为true，则说明可以恰好将背包装满，若x为false，则说明不能恰好将背包装满。

• 步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)

与上面类似，这里就直接给出来了：

1.不把这第i个物品装入背包：dp[ i ][ j ] = dp[ i - 1 ][ j ]
2.把这第i个物品装入背包：dp[ i ][ j ] = dp[ i - 1][ j - nums[ i - 1 ] ]

• 第三步骤：找出初始值（base case）：

当背包容量为0时（sum / 2= 0）这时无论物体有多少个都可以满足条件，就是什么都不装嘛

ok，接下来看完整代码：

boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    // 和为奇数时，不可能划分成两个和相等的集合
    if (sum % 2 != 0) return false;
    int n = nums.length;
    sum = sum / 2;
    boolean[][] dp = new boolean[n + 1][sum + 1];
    // base case
    for (int i = 0; i <= n; i++)
        dp[i][0] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (j - nums[i - 1] < 0) {
                // 背包容量不足，不能装入第 i 个物品
                dp[i][j] = dp[i - 1][j];
            } else {
                // 装入或不装入背包
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }
    return dp[n][sum];
}

完全背包问题：

完全背包问题与0-1背包问题类似，但不同之处在于每个物品可以选择放入背包多次（数量无限），即每个物品的选择是一个无限的选择。我们给出对应的解题方法：

• 步骤一:定义dp数组元素的含义：

若只使用前i个物品（可以重复使用），当背包容量为j时，能装入背包的最大价值为dp[i][w]

• 步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)

1.不将第i个物品装入背包，此时：dp[ i ][ w ] = dp[ i - 1 ][ w ]
2.将第i个物品装入背包，此时:dp[ i ][ w ] = dp[ i ][ w -wt[ i - 1] ] + val[ i - 1 ]

• 第三步骤：找出初始值（base case）：

这题与0 - 1的bas背包的base case 一致，当物品个数为0或者背包当前容量为0时，dp[ i ][ w ] 都等于0

对应的动态规划代码为：

int fullBackpack(int W, int N, int[] wt, int[] val) {
    assert N == wt.length;
    // base case 已初始化，数组自动全部初始化为0
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                // 这种情况下只能选择不装入背包
                dp[i][w] = dp[i - 1][w];
            } else {
                // 装入或者不装入背包，择优
                dp[i][w] = Math.max(
                    dp[i][w - wt[i-1]] + val[i-1],
                    dp[i - 1][w]
                );
            }
        }
    }
    return dp[N][W];
}

完全背包类问题 零钱兑换II:

这是力扣第 518 题「零钱兑换 II」，题目描述：

给定不同面额的硬币coins和一个总金额amount，写一个函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。对应函数签名如下：

我们可以把这个问题转化为完全背包问题的描述形式：

有一个背包，最大容量为amount，有一系列物品coins，每个物品的重量为coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？按照动态规划三步走：

• 步骤一:定义dp数组元素的含义：

dp[i][j]的定义如下：若只使用前i个物品（可以重复使用），当背包容量为j时，有dp[i][j]种方法可以装满背包。

• 步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)

1.如果你不把这第i个物品装入背包，也就是说你不使用coins[i-1]这个面值的硬币，那么凑出面额j的方法数dp[i][j]应该等于dp[i-1][j]，继承之前的结果
即状态转移方程为：dp[ i ][ j ] = dp[ i -1 ][ j ]

2.如果你把这第i个物品装入了背包，也就是说你使用coins[i-1]这个面值的硬币，那么dp[i][j]应该等于dp[i][j-coins[i-1]]。

即状态转移方程为：dp[ i ][ j ] = dp[ i ][ j - coins[ i - 1] ]

• 第三步骤：找出初始值（base case）：

base case 为dp[0][..] = 0, dp[..][0] = 1 。

i = 0代表不使用任何硬币面值，这种情况下显然无法凑出任何金额；
j = 0代表需要凑出的目标金额为 0，那么什么都不做就是唯一的一种凑法。

写出动态规划代码：

int change(int amount, int[] coins) {
    int n = coins.length;
    int[][] dp = int[n + 1][amount + 1];
    // base case
    for (int i = 0; i <= n; i++)
        dp[i][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= amount; j++)
            //装入背包或者不装入，加起来
            if (j - coins[i-1] >= 0)
                dp[i][j] = dp[i - 1][j]
                          + dp[i][j - coins[i-1]];
            else // < 0 只能选择不装入背包
                dp[i][j] = dp[i - 1][j];
    }
    return dp[n][amount];
}

结语：

本文详细介绍了动态规划中背包问题的两种主要类型：0-1背包问题和完全背包问题。通过具体的例子和代码实现，帮助读者理解动态规划的基本思想和解题步骤。希望这篇文章能帮助你在算法学习的道路上更进一步。

本文原文来自金斗云，原始发布日期为2024年8月7日。