动态规划问题一直是算法中的难点和重点之一，而三类背包问题使用的动态规划思想本质上是一样的，下面我会通过背包问题解释如何用动态规划求解，如果觉得文字太啰嗦可以直接看代码。
01背包问题
有n个物品，每个物品有体积和价值两个属性，现在有一个固定容量的背包，要将这些物品放入背包内，使得背包内物品总价值最大，问要如何放？
注意：这里每个物品的数量为1。
设$V = 14$。
为了描述方便起见，我们用$c_1,c_2,c_3,....c_n$表示物品的体积， 用$w_1,w_2,w_3,....w_n$表示物品的价值，用$V$表示背包的容量，$n$表示物品的数量。
动态规划描述
背包问题是动态规划问题的一种，和分治算法一样，它是将一个大问题分成一个一个的小问题，然后找到大问题和小问题之间的递推式，将一个个小问题组合成大问题，
并且通常要求这些小问题也要达到最优。能用动态规划解决的问题一般含有两种性质：最优子结构和重叠子问题。动态规划从本质上讲就是穷举法， 但是它的却比一般的算法效率要高，这就是因为它能剪去重叠的子问题，使得总体复杂度不那么高。
解决方法
1.递归方法
我们先从最容易入手的地方开始，用递归的方法来解这个问题。
首先对于每个物品，我们的选择只有两个：放或者不放。我们将所有的可能都穷举出来，就可以得到下面这个树状图（只画了前四个结点）：
这个树上每一个分支都只能选一个，每一行就代表一个子问题。我们用$F(i, v_i)$表示前$i$个物品放入背包内的最大价值（即最优方案），此时这个$v_i$指的是放入前$i$个物品后背包剩余的容量。
显而易见$F(5, v_5)$就是我们要解的大问题，分割一下子问题就是：$F(1, v_1)$, $F(2, v_2)$, $F(3, v_3)$, $F(4, v_4)$。要解决这个大问题，我们就得先解决它的前面一个子问题$F(4, v_4)$（求解原问题时子问题也要达到最优，所以该问题具有最优子结构，这是判断问题能否用动态规划解的条件之一）。
至于为什么解决$F(5, v_5)$问题之前要先解决$F(4, v_4)$，这是因为对于问题$F(5, v_5)$来说，如果解决了问题$F(4, v_4)$剩下就只需要判断最后一个物品体积是否比剩余背包容量大，是直接放入背包，否则就不放。
而对于子问题$F(4, v_4)$，我们得解决$F(3, v_3)$....从而得解决$F(1, v_1)$。对于子问题$F(1, v_1)$，由于它前面没有子问题，所以解决它只需要判断$c_1 le V$是否成立。
所以对于每一个子问题，由于前面的子问题已被解决，因此我们都只需要做两个选择：放，还是不放。
假设我们已经知道了前$i-1$个物品放入背包的最优方案$F(i-1, v_{i-1})$，那么对于第$i$个物品要放入背包就有三种情况：
若物品的体积$c_i$大于背包剩余的容量$v_{i-1}$，那么只能丢弃这个物品：
$F(i, v_i) = F(i-1, v_{i-1})$
否则就有两种选择：
1. 不放第$i$个物品：
$F(i, v_i) = F(i-1, v_{i-1})$
2. 放第$i$个物品：
$F(i, v_i) = w_i + F(i-1, v_{i-1}-c_i)$
要从这两个方案中选择总价值最大的，所以：
用Python实现代码如下：
2.动态规划方法
递归方法最大的缺点就在于有较多重复的计算，通过上面的树状图可以知道，递归会遍历这棵树的所有结点，所以它的时间复杂度为：$O(2^{n})$。
指数阶的时间复杂度对于计算机来说简直就是灾难！那有没有什么办法减少这些重复的计算呢？这就是接下来要说的动态规划，它可以通过存储已经计算出来的结果来减少重叠子问题。
和递归一样，动态规划也是要找出所有可能的情况并从中选出最优的，但不同的是动态规划每次计算都会将结果存储在一个表中，下一次遇到同样的问题时就直接查表，而不必重复计算。
为了方便描述，我们重新将$F(i, V)$定义为前$i$个物品在总容量为$V$背包里的最大价值（注意和这里的$V$指的是背包总容量并非剩余容量）。那么现在的大问题就是$F(5, 14)$，按照上面递归的思想，改写一下式子就是：
对于动态规划通常我们会用自底向上的方法，而递归是自顶向下的。自底向上的意思就是我们从子问题$F(0, 0)$一直计算到$F(5, 14)$，我们知道要计算$F(5, 14)$，得先解决它前面的子问题，但由于是自底向上的，所以我们并不知道$F(5, 14)$的子问题有哪些，因此我们只能够把它所有可能的子问题都找出来，即$F(4, V), (V in (0, 1, 2, 3......14))$，而$F(5, 14)$的子问题一定是包含在内的，比如$F(5, 14)$的子问题就是$F(4, 14)$和$F(4, 14-c_5)$。所以自顶向下的过程就相当于在填这个表：
表一旦填完，答案也就出来了。
算法的时空复杂度都是：$O(n imes V)$，并且如果$V$足够小，可进一步降低至线性($O(n)$)，比递归方法要高效地多。
空间复杂度优化：根据递推式可知，第$i$个子问题只与第$i-1$个子问题有关，因此我们用两个列表来存储第$i$个和第$i-1$个子问题，每当前面一个子问题求解完，我们就用另一个列表来存下一个子问题。
此时空间复杂度为$O(2V)$。
完全背包问题
这里还是以01背包的例子为例，除了每个物品可取放的数量是无限的，其他条件不变。现在对于每件物品来说，能做的选择变多了，之前要么放要么不放；现在是不放和放多少个。也就是说递推式现在应该有多个选择，对于递归解法，根据上面01背包递归解法的递推式，这里要能使得$F(i, V)=w_i +F(i-1, V-c_i)$对于每个物品都能重复进行多次，而不是一次就结束了；对于动态规划解法，在一个子问题$F(i, j)$内(即第二层for循环里)，可以设计一个for循环来计算在这个容量下最多可以放几个同类的物品。
用Python实现的代码如下：
动态规划解法我没有优化空间，可以自行用上面的方法进行优化。
多重背包问题
问题描述：与完全背包不同的地方在于，现在每件物品都有一个固定的数量，仍然是求在特定的背包容量下的最大放进背包的物品价值。解法：明白了完全背包，多重背包问题就非常简单了。它的解决方法和完全背包问题基本相同，完全背包问题需要计算在固定容量下，每件物品能拿放的数目，对于一个固定背包容量，每件物品可以拿很多个（只要不超出背包的总容量就可以），但是在多重背包，每件物品的数量是固定的，有限的。所以就是在这基础上多加个限定条件，就是：每件物品可以拿多个，但不能超过最大限制的数量，同时也不能超过背包的总容量。也就是说之前完全背包的最大数量是$+infty$，现在将最大数量修改成对应每件物品的数量即可。递归方法：控制$F(i, V)=w_i +F(i-1, V-c_i)$的最大递归次数不能大于物品数量；动态规划方法：给while循环设置条件使得它的重复次数不能大于物品的个数。
代码我测试了几个例子没有发现问题，如果有错误可以在评论区告诉我。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/3908.html