代码随想录day42和day43动态规划模块01背包问题“即使到不了远方，心中也要有远方的模样。”文章目录1.01背包理论基础1.1什么是背包问题1.2二维dp数组01背包1.3一维dp数组(滚动数组)01背包2.leetcode416.分割等和子集2.1详细思路及思考难点2.2具体步骤及代码实现3.leetcode1049.最后一块石头的重量3.1详细思路及思考难点3.2具体步骤及代码实现4.leetcode494.目标和4.1详细思路及思考难点4.2具体步骤及代码实现5.leetcode474.一和零5.1详细思路及思考难点5.2具体步骤及代码实现1.01背包理论基础1.1什么是背包问题
代码随想录day42和day43动态规划模块01背包问题“即使到不了远方，心中也要有远方的模样。”文章目录1.01背包理论基础1.1什么是背包问题1.2二维dp数组01背包1.3一维dp数组(滚动数组)01背包2.leetcode416.分割等和子集2.1详细思路及思考难点2.2具体步骤及代码实现3.leetcode1049.最后一块石头的重量3.1详细思路及思考难点3.2具体步骤及代码实现4.leetcode494.目标和4.1详细思路及思考难点4.2具体步骤及代码实现5.leetcode474.一和零5.1详细思路及思考难点5.2具体步骤及代码实现1.01背包理论基础1.1什么是背包问题
收录一些比较冷门的DP优化方法。1.树上依赖性背包树上依赖性背包形如在树上选出若干个物品做背包问题，满足这些物品连通。由于01背包，多重背包和完全背包均可以在\(\mathcal{O}(V)\)的时间内加入一个物品，\(\mathcal{O}(V^2)\)的时间内合并两个背包，所以不妨设背包类型为多重背包。先考虑一个弱化版问题。给定一棵有根树，若一个节点被选，则它的父亲必须被选。显然存在一个\(\mathcal{O}(nV^2)\)的树形DP做法，它能求出以每个节点为根时其子树的答案。接下来引出科技：树上依赖性背包。我们发现对每个节点都求答案似乎有些累赘，因为我们只关心以\(1\)为根时的答案
收录一些比较冷门的DP优化方法。1.树上依赖性背包树上依赖性背包形如在树上选出若干个物品做背包问题，满足这些物品连通。由于01背包，多重背包和完全背包均可以在\(\mathcal{O}(V)\)的时间内加入一个物品，\(\mathcal{O}(V^2)\)的时间内合并两个背包，所以不妨设背包类型为多重背包。先考虑一个弱化版问题。给定一棵有根树，若一个节点被选，则它的父亲必须被选。显然存在一个\(\mathcal{O}(nV^2)\)的树形DP做法，它能求出以每个节点为根时其子树的答案。接下来引出科技：树上依赖性背包。我们发现对每个节点都求答案似乎有些累赘，因为我们只关心以\(1\)为根时的答案
题目传送门：https://www.luogu.com.cn/problem/P1073思路：首先，我们目的是想要在图上dp求最优的路线，但是原图上会存在环，那么我们就要先通过tarjan缩点，将所有环缩成一个点，同时，记录每个点的最大值和最小值，缩点得到DAG后，我们可以在DAG上进行dp，每次转移有三种方式，一是保留上一个点的dp值，二是求得目前所在点的值，三是这个点本身的dp值，三者取最大就ok了。还要注意的是，在建DAG图的时候，要记录每个点的入度，在之后的dp过程中，每一个点在全部走到的时候，才能压入队列，进行更新操作，保证dp内的值是最优的，也就是无后效性。代码：1#include
题目传送门：https://www.luogu.com.cn/problem/P1073思路：首先，我们目的是想要在图上dp求最优的路线，但是原图上会存在环，那么我们就要先通过tarjan缩点，将所有环缩成一个点，同时，记录每个点的最大值和最小值，缩点得到DAG后，我们可以在DAG上进行dp，每次转移有三种方式，一是保留上一个点的dp值，二是求得目前所在点的值，三是这个点本身的dp值，三者取最大就ok了。还要注意的是，在建DAG图的时候，要记录每个点的入度，在之后的dp过程中，每一个点在全部走到的时候，才能压入队列，进行更新操作，保证dp内的值是最优的，也就是无后效性。代码：1#include
01背包面试题系列（一）题目描述——分割等和子集给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例1：输入：nums=[1,5,11,5]输出：true解释：数组可以分割成[1,5,5]和[11]。示例2：输入：nums=[1,2,3,5]输出：false解释：数组不能分割成两个元素和相等的子集。01背包动态规划求解上面的问题乍一看好像是一个子集划分的问题，我们可能根据数据nums得到它的所有的子集，然后将所有的自己加起来看看是否存在一个子集的数据的和等于nums数组所有数据的和的一半，其实我们确实可以这样做，我们将在后文当中仔细探
01背包面试题系列（一）题目描述——分割等和子集给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例1：输入：nums=[1,5,11,5]输出：true解释：数组可以分割成[1,5,5]和[11]。示例2：输入：nums=[1,2,3,5]输出：false解释：数组不能分割成两个元素和相等的子集。01背包动态规划求解上面的问题乍一看好像是一个子集划分的问题，我们可能根据数据nums得到它的所有的子集，然后将所有的自己加起来看看是否存在一个子集的数据的和等于nums数组所有数据的和的一半，其实我们确实可以这样做，我们将在后文当中仔细探
深入剖析多重背包问题（上篇）前言在前面的两篇文章当中，我们已经仔细的讨论了01背包问题和完全背包问题，在本篇文章当中将给大家介绍另外一种背包问题——多重背包问题，多重背包问题的物品数量介于01背包问题和完全背包问题之间，他的物品的数量是有限个！多重背包问题介绍有\(N\)种物品和一个容量是\(V\)的背包。第\(i\)种物品最多有\(s_i\)件，每件体积是\(v_i\)，价值是\(w_i\)。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。注意：上面使用到的字符含义在本篇文章当中都一样。多重背包问题跟01背包和完全背包的区别都是在物品的可用次数上，01背包只能使用一次
深入剖析多重背包问题（上篇）前言在前面的两篇文章当中，我们已经仔细的讨论了01背包问题和完全背包问题，在本篇文章当中将给大家介绍另外一种背包问题——多重背包问题，多重背包问题的物品数量介于01背包问题和完全背包问题之间，他的物品的数量是有限个！多重背包问题介绍有\(N\)种物品和一个容量是\(V\)的背包。第\(i\)种物品最多有\(s_i\)件，每件体积是\(v_i\)，价值是\(w_i\)。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。注意：上面使用到的字符含义在本篇文章当中都一样。多重背包问题跟01背包和完全背包的区别都是在物品的可用次数上，01背包只能使用一次
