背包问题例题讲解



动态规划——背包问题

理解背包问题：分类与解题模板

在算法问题中，背包问题是一类经典的动态规划问题，它们的核心思想是选择一组物品，满足某个条件或目标。背包问题不仅限于物理意义上的“背包”和“物品”，其概念可以扩展到许多实际场景，如资金分配、时间管理、资源优化等。

什么是背包问题？

背包问题可以定义为：给定一个背包容量（）和一组物品（），能否按某种方式选取中的元素，使其总和或总重量等于？

注意：

1. 背包容量和物品可以是数值或其他类型（如字符串）。
2. 目标值（target）可以是显式给出，也可能需要我们从题目中推导（如等）。
3. 选择方式包括：每个物品最多选一次、每个物品可以多次选择、物品顺序有无影响等。

背包问题的分类

背包问题可以根据选择方式和问题类型进行分类。

按选择方式分类：

1. 0/1背包问题：每个物品最多选取一次。
2. 完全背包问题：每个物品可以重复选择。
3. 组合背包问题：背包中的物品顺序重要，选择时要考虑排列组合。
4. 分组背包问题：多个背包，每个背包内的物品只能选择一个，需要遍历每个背包。

按问题类型分类：

1. 最值问题：求最大值或最小值。
2. 存在问题：是否存在某种组合满足条件。
3. 组合问题：求所有满足条件的排列组合数。

综合分类：

通过将选择方式与问题类型结合，可以得到如下常见的背包问题类型：

1. 0/1 背包最值问题
2. 0/1 背包存在问题
3. 0/1 背包组合问题
4. 完全背包最值问题
5. 完全背包存在问题
6. 完全背包组合问题
7. 分组背包最值问题
8. 分组背包存在问题
9. 分组背包组合问题

背包问题解题模板

解决背包问题的基本方法是动态规划。解题的核心是设置一个数组，记录每种状态下的最优解，然后通过遍历物品和背包容量来更新。

基本解题思路：

1. 二维动态规划：定义表示从前个物品中选择不超过重量的最大价值。
2. 一维动态规划：通过去掉物品的那一层，简化成表示容量为的背包能放下的最大价值。

模板代码：

以经典的0/1背包问题为例，最基础的二维动态规划代码如下：

一维动态规划的简化代码如下：

分类解题模板：

根据背包问题的分类，解题时可以选择合适的遍历顺序和状态转移方程：

• 0/1背包：外循环物品，内循环容量（倒序）。
• 完全背包：外循环物品，内循环容量（正序）。
• 组合背包：外循环容量，内循环物品（正序）。
• 分组背包：三重循环，外层遍历背包，内层根据题目要求选取合适的背包类型。

状态转移方程的写法也因问题类型不同而有所变化：

• 最值问题：。
• 存在问题：。
• 组合问题：。

例题解析

通过几个例题来具体说明如何应用背包问题的分类与模板：

1. 最后一块石头的重量 II（1049. 最后一块石头的重量 II）—— 01背包的最值问题。
2. 零钱兑换（322. 零钱兑换）—— 完全背包的最值问题。
3. 分割等和子集（416. 分割等和子集）—— 01背包的存在问题。

注意：
1、背包容量target和物品nums的类型可能是数，也可能是字符串
2、target可能题目已经给出(显式)，也可能是需要我们从题目的信息中挖掘出来(非显式)(常见的非显式target比如sum/2等)
3、选取方式有常见的一下几种：每个元素选一次/每个元素选多次/选元素进行排列组合
那么对应的背包问题就是下面我们要讲的背包分类

二维代码可以进行优化，去除选取物品的那一层，简化为一维背包
// 一维
//状态定义：dp[j]表示容量为j的背包能放下东西的最大价值

分类解题模板
背包问题大体的解题模板是两层循环，分别遍历物品nums和背包容量target，然后写转移方程，
根据背包的分类我们确定物品和容量遍历的先后顺序，根据问题的分类我们确定状态转移方程的写法

首先是背包分类的模板：
1、0/1背包：外循环nums,内循环target,target倒序且target>=nums[i];
2、完全背包：外循环nums,内循环target,target正序且target>=nums[i];
3、组合背包：外循环target,内循环nums,target正序且target>=nums[i];
4、分组背包：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板

然后是问题分类的模板：
1、最值问题: dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);
2、存在问题(bool)：dp[i]=dp[i]||dp[i-num];
3、组合问题：dp[i]+=dp[i-num];

这样遇到问题将两个模板往上一套大部分问题就可以迎刃而解

1049. 最后一块石头的重量 II

322. 零钱兑换

416. 分割等和子集

494. 目标和

279. 完全平方数

1155. 掷骰子等于目标和的方法数

518. 零钱兑换 II

总结

背包问题看似千变万化，但它们的本质都是在给定条件下选择物品的最优问题。通过掌握背包问题的分类和解题模板，我们可以迅速识别并解决相关问题。希望这篇文章能帮助大家更好地理解和应用背包问题。

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/11106.html