动态规划-----背包类问题（0-1背包与完全背包）详解
admin目录
什么是背包问题？
动态规划问题的一般解决办法：
0-1背包问题：
0 - 1背包类问题 分割等和子集：
完全背包问题：
完全背包类问题 零钱兑换II:
什么是背包问题？
背包问题(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 题「分割等和子集open in new window」：
题目描述：输入一个只包含正整数的非空数组 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 题「零钱兑换 IIopen in new window」，题目描述：
给定不同面额的硬币 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]; } 结语： 写博客不仅仅是为了分享学习经历，同时这也有利于我巩固自己的知识点，总结该知识点，由于作者水平有限，对文章有任何问题的还请指出，接受大家的批评，让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注，你们的鼓励是我创作的最大动力！
TAG：0-1背包问题
