算法训练Day42 | 01背包问题的理论基础（二维和一维dp数组的全面剖析）；LeetCode416. 分割等和子集（01背包的应用）

目录

01背包问题的理论基础

方法一：二维dp数组01背包

1. 思路

2. 代码实现

3. 复杂度分析

4. 思考与收获

方法二：一维dp数组01背包（滚动数组）

1. 思路

2. 代码实现

3. 复杂度分析

4. 思考与收获

LeetCode416. 分割等和子集

1. 思路

2. 代码实现

3. 复杂度分析

4. 思考与收获

---

01背包问题的理论基础

 背包问题系列：

对于面试的话，其实掌握01背包，和完全背包，就够用了，最多可以再来一个多重背包；至于其他背包，面试几乎不会问，都是竞赛级别的了，leetcode上连多重背包的题目都没有，所以题库也告诉我们，01背包和完全背包就够用了；

而完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的，**所以背包问题的理论基础重中之重是01背包，一定要理解透！**leetcode上没有纯01背包的问题，都是01背包应用方面的题目，也就是需要转化为01背包问题。所以我先通过纯01背包问题，把01背包原理讲清楚，后续再讲解leetcode题目的时候，重点就是讲解如何转化为01背包问题了。

题目描述

（LeetCode上没有纯粹的01背包问题）

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

 

方法一：二维dp数组01背包

1. 思路

这是标准的背包问题，以至于很多同学看了这个自然就会想到背包，甚至都不知道暴力的解法应该怎么解了。这样其实是没有从底向上去思考，而是习惯性想到了背包；

那么暴力的解法应该是怎么样的呢？

每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是o(2^n)，这里的n表示物品数量。所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！

讲解所用到的例子：

背包最大重量为4，物品如下：

问背包能背的物品最大价值是多少？以下讲解和图示中出现的数字都是以这个例子为例。<