PART1 楔子

01 因为背包问题是一个经典问题。很多文章直接写出了经典的解题思路。然而，这常常使人忘记。让某人记住某件事的最好方法是确保他们从里到外理解它。在这篇文章中，我们将从最简单的暴力枚举、递归等方法开始，一步步分析各个方法的优化点。文末提供了详细代码地址。我希望这对你有帮助。

PART2 问题描述

现在我们有一个背包（容器），体积（容量）为V。现在有N 种物品（每种物品只有一种）。每一项的值为W[i]，占用的空间为W[i]。输入给出的值为C[i]。该背包最多可携带的物品总价值是多少？

首先，我们来快速分析一下这个问题。每个项目只有一个。换句话说，对于任何项目，您要么选择它，要么不选择它。

正如文章开头提到的，首先使用最简单的暴力枚举方案来分析问题，找到方案的缺点，然后继续分析更好的方案。

PART3 朴素的暴力算法

是否选择第一项可以通过允许下次处理第i项时处理完处理后的前两项来轻松解决。通过这样按住，您可以找到处理前n 项后得到的最大总值。

递归算法

分析：

利用递归的思想，如果我们现在从最后一个物体中选择，并且这个物体的重量大于背包的重量，我们可以从第n-1个物体开始选择。

如果这个东西的重量小于你的背包，你将面临两种选择：

1. 如果没有选择，可以跳过此项，从n-1中选择。

2. 选择后，背包的重量将会减少，您可以保存该值并继续选择下一个背包。

最后，我们比较n、n-1、 到0 的值。给定一个比较大小的函数，它会打印最大值。

（PS:详细代码请见文末）

（PS:详细代码请见文末）

暴力枚举

思路分析：

首先，我们根据项目数量生成所有子集组合。 01 矩阵。这是一个二维数组。接下来进行矩阵遍历判断。判断每层的容量是否超过背包的容量，并确定最大值。还有一种使用格雷码生成子集组合的方法。我这里暂时不做详细介绍。如果您的朋友有兴趣，请自行研究。

（PS:详细代码请见文末）

PART4 动态规划的原理及过程

1、原理

动态规划将一个大问题划分为更小的问题，通过寻找大问题和小问题之间的递归关系来解决每个小问题，最终达到解决原问题的效果。然而，不同之处在于，分而治之的方法对于子问题、子子问题等等会一遍又一遍地重复。动态规划的记忆方式是填表，记录所有已解决的子问题的答案，并保存不同阶段的不同状态，以便在新问题中使用。可以直接提取，避免重复计算，节省时间。

因此，用动态规划解决问题的核心在于，一旦问题满足最优性原则，填表就会找到最优解。

2. 分析过程

a) 01 背包问题的抽象

（X1，X2，…，Xn，Xi可以为0或1，表示第i项是否被选中）

Vi表示第i个物品的价值，Wi表示第i个物品的体积（重量）。

b) 建立模型

即求max(V1X1+V2X2+…+VnXn)。

c) 限制条件

W1X1+W2X2+…+WnXn 容量

d) 定义V(i,j)。

当前背包容量j，前i个物品的最优组合对应的值。

e) 最优性原理是动态规划的基础

最优性原则指出[多步决策过程中的最优决策序列具有以下属性：

无论初始状态还是第一个决策，对于前一个决策引起的某个状态，

后续阶段的决策顺序必须构成最优策略。 ]

判断问题是否满足最优性原则，并用反证法证明：

假设(X1,X2,…,Xn)是01背包问题的最优解。

在这种情况下，(X2, X3,…,Xn) 是该子问题的最优解。

假设(Y2,Y3,Yn)是上述问题的子问题的最优解。

那么应该有

(V2Y2+V3Y3+.+VnYn)+V1X1(V2X2+V3X3+.+VnXn)+V1X

且(V2X2+V3X3+…+VnXn)+V1X1=(V1X1+V2X2+…+VnXn)

然后我们有(V2Y2+V3Y3+…+VnYn)+V1X1 (V1X1+V2X2+…+VnXn)。

该方程表明(X1,Y2,Y3,Yn)是01背包问题的最优解。

这与第一个假设相矛盾，即(X1, X2,Xn) 是01 背包问题的最优解。

因此，01背包问题满足最优性原则。

f) 求递推公式

当前的产品有两种可能性。

首先，袋子的容量小于产品的体积，因此无法装载。此时的值与第i-1个值相同，即V(i,j)=V。 (i-1,j);

然后，您有足够的空间来存储该产品，但即使安装了也不一定达到当前的最佳状态，因此选择最佳选项：安装或不安装。

V(i,j)=max{V(i-1,j), V(i-1,j-w(i))+v(i)}

其中，V(i-1,j)表示不装载，V(i-1,j-w(i))+v(i)表示装载第i个产品，背包的容量减少w (i)，但其值增加v(i)。

由此我们可以推导出递归关系。

1) jw(i) V(i,j)=V(i-1,j)

2) j=w(i) V(i,j)=max{V(i-1,j), V(i-1,j-w(i))+v(i)}

g) 填写表格

首先，初始化边界条件V(0,j)=V(i,0)=0。

（注：数量：数量=4，背包容量：容量=8）

（注：横轴为背包容量，纵轴为所选产品下标）

h) 填完表格后，最优解为：V(数量，容量)=V(4,8)=10

3. 二维数组动态规划

（PS:详细代码请见文末）

4. Backpack使用滚动数组来压缩空间

所谓滚动阵列的目的就是为了优化空间。从上面的解法我们可以看出，在求解过程中，状态转移矩阵使用了N*V数组。当涉及到以前的状态解决方案时，以前存储的状态信息是无用的，可以丢弃，所以我们只需要空间来存储当前状态和以前的状态，所以我们需要做的就是2*V空间。它以循环滚动的方式达到了与N*V相同的目的。效果一样。这是一个非常大的空间优化。

这是代码：您可以在每个内部循环之后打印当前状态解决方案。比较上面使用二维数组的状态转移矩阵的输出，可以看到将输出重定向到文本具有相同的效果。它将帮助您更好地理解。

（PS:详细代码请见文末）

5.背包空间降维优化——一维数组

1.什么是空间优化以及为什么需要它？

01 Backpack让我们通过优化数组（使用滚动数组的方法）将原来的N*V的空间复杂度降低到V。也就是说，您可以删除与该项目关联的N。

为什么需要空间优化，首先是因为递归消耗的空间比较大，因为它本质上是用空间换时间。其次，算法竞赛一般都有场地限制。你总会被问到一些优化问题。在面试中养成优化的习惯也有好处。

2.为什么这个问题可以降维？

通过观察，我们发现在正常版本的01背包递归中，f[i][.]只与f[i-1][.]相关，并且一职业一职业都可以使用。滚动这种方法称为滚动数组，因为它重用了数组中的空间。滚动并直接覆盖不再使用的数据。

滚动数组的缺点是它们的代价是擦除大量数据。可能不是所有问题都可用，但这里答案是递归的最后一步，所以递归后可以直接打印。无需调用不再是数据的内容。

（PS:详细代码请见文末）

PART5 背包恰好装满

有两种类型的初始化：一种只需要最大值，一种需要完整输入。第一种类型的初始化是将值赋给0。第二种类型的初始化是将一个值赋给负无穷大。该数据实际上并不存在。换句话说，这并不是一个不存在的数字。这已经实现，并且没有与该数字相关的可用数据。

PART6 背包输出最优方案

一般来说，背包问题就是寻找最优值。然而，如果你想输出一个产生这个最优值的解，你可以根据状态转移方程推回，从这个状态找到前一个状态，然后按顺序推入。

因此，有两种实现方法，原理是一样的：直接根据状态转移矩阵进行，并使用附加的状态矩阵来记录最优解路径。

PART7 拓展延升

在上面的分析过程中，我们最终采用了动态规划的思想进行分析。那么，你对动态规划了解多少呢？还有哪些与动态规划类似的分析技术，各自有什么特点呢？下面我们将一一解释。 （PS:动态规划算法最复杂，但也是最有效的，所以我们最后讨论）

分而治之算法

分治算法是最容易与动态规划混淆的算法。然而，它们之间存在重要的差异。稍后会详细介绍。

算法思想：将原问题拆分成几个与原问题结构相似的较小的子问题，递归地求解这些子问题，并结合结果来求解原问题的解，得到特征。问题的规模缩小了。在某种程度上解决问题是很容易的。也就是说，该问题具有最优子结构属性。您可以使用问题来组合分解问题的解决方案。每个分解的子问题都是相互独立的。换句话说，子问题和动态规划最大的区别在于它们不包含子问题。分而治之的问题是相互独立的，不涉及共同的子问题。贪心算法

算法思维：通过在算法中的每个决策点做出最佳选择，得出特定问题的最佳解决方案。这种启发式策略并不总是能产生最佳解决方案。步骤：将优化问题转化为这样的问题。也就是说，我们首先做出选择，然后解决剩余的子问题，以证明原问题总是有一个可以通过贪婪选择获得的最优解。贪婪选择的安全性这表明，在做出贪婪选择后，剩余的子问题具有这样的性质。也就是说，通过将问题的最优解与我们所做的贪心选择相结合，我们得到了原问题的最优解。要素：贪婪选择属性、最优子结构属性贪婪选择属性：通过局部（贪婪）选择可以得到全局最优解。动态规划

算法思想：类似于分而治之，通过组合子问题的解来解决整个问题。不同之处在于，动态规划适合分解通常不相互独立的子问题。在这种情况下，使用分而治之的方法会导致某些子问题被多次计算，而动态规划可以通过记录已解决的子问题来避免重复计算。步骤：递归定义最优解值，并根据计算结果构造最优解值元素。最优子结构。子问题：010 -1010 开始学习动态规划算法，直到完成本文。我敏锐地意识到，我不能放弃在学校学到的数学归纳、数学推导、分析思维。除非你再次拿起它，否则这将很难理解。最近，我开始补充数学知识。

关于背包问题，了解01背包的概念很重要。 01背包的想法也适用于完整背包、多充电背包和混合背包等挑战，我们接下来将进行分析。我们要做的就是学会推导和实现状态转移方程，学会优化空间复杂度和降维。

以后我会继续更新关于背包的文章。敬请期待。也欢迎指正。

文中代码地址：附评论区