动态规划经典问题《背包问题》,弄懂这个你就懂了动态规划

2023年8月1日发(作者：)

动态规划经典问题《背包问题》，弄懂这个你就懂了动态规划背包九讲背包问题是动态规划问题中最为经典的问题之⼀，可以说完全弄明⽩了背包问题，能够很⼤程度上帮助我们了解动态规划转移⽅程的基本推导。背包问题的经典讲义为浙江⼤学崔添翼同学撰写的《背包九讲》，本⽂是我阅读该⽂章过程中的笔记和感想。动态规划的思路其实并不难想到，⼤多数问题只需要看⼀眼就能知道是否可以采⽤动规求解了，难点在于如何推导出合适的状态矩阵和状态转移⽅程。这需要我们多⼿写DP表，仔细找规律。动态规划问题基本概念动态规划⽅法要寻找符合“最优⼦结构“的状态和状态转移⽅程的定义，在找到之后，这个问题就可以以“记忆化地求解递推式”的⽅法来解决。⽽寻找到的定义，才是动态规划的本质。⼀般来说，当问题具有以下三个特点的时候，适⽤动态规划⽅法解决：最优⼦结构： ⼤问题的最优解可以由⼩问题的最优解推出⽆后效性： 如果给定某⼀阶段的状态，则在这⼀阶段以后过程的发展不受这阶段以前各段状态的影响。重叠⼦问题：相同的⼦问题可能被重复求解多次其实，上述前两个特点准确说是分治算法的特点。动态规划和递归算法本质上都是分治算法的⼀个⼦集，它们都是将⼤问题分解为⼩问题进⾏求解。⽽第三个特点区分了使⽤递归和使⽤动态规划的情况：⼀般来说，⼦问题独⽴的情况我们使⽤递归算法解决即可，⽽⼦问题重叠必须使⽤动态规划，否则时间复杂度会⼤⼤升⾼。我们以最简单的斐波那契数列为例，当求解第101项时，我们需要计算第100项和第99项，⽽当求解第102项时，我们需要求解100项和第101项。如果我们直接使⽤递归算法，那么求解第101项和第102项会重复计算第100项两次，这将⽩⽩浪费许多时间。实际上，如果我们对递归算法稍作修改，就可以让其变为动态规划的形式，即另加⼀个⽤于记忆的数据结构。这种做法叫做记忆化搜索，它本质上就是⼀种⾃顶向下的动态规划算法（从⼤问题到⼩问题）。如果我们从⼩问题开始求解，最终递推出所要求的⼤问题结果，那么这也是⼀种动态规划的实现⽅法（⾃底向上）。有不少博客都将记忆化搜索和⾃底向上的动态规划区分开来，将后者定义为动态规划，实际上我认为⼆者都是动态规划的不同实现形式。如果我们使⽤动态规划算法，它将在计算的过程中将得到的第100项的结果存储起来，从⽽避免重复计算，这也是为什么动态规划算法能够⼤⼤减少运⾏时间的原因。动态规划算法的关键点总结为：动态规划法试图只解决每个⼦问题⼀次⼀旦某个给定⼦问题的解已经算出，则将其记忆化存储，以便下次需要同⼀个⼦问题解之时直接查表。动态规划算法往往还会被拿来和贪⼼算法⽐较，但贪⼼算法只会关注局部最优解，当局部最优⽆法达到全局最优时，贪⼼算法将出错。实际上，如何选择各种策略可以总结为：每个阶段只有⼀个状态->递推；每个阶段的最优状态都是由上⼀个阶段的最优状态得到的->贪⼼；每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到⽽不管之前这个状态是如何得到的->动态规划。同时，我们也要注意，尽管动态规划具有⽆后效性，但并不代表我们不可以⽤动态规划解决求解需要获取过程组合的问题，例如：140. 单词拆分 II。0-1背包问题题⽬有 N 件物品和⼀个容量为 V 的背包。放⼊第 i 件物品耗费的费⽤是C1i，得到的价值是Wi。求解将哪些物品装⼊背包可使价值总和最⼤。基本思路最基础的背包问题，每件物品只有1个，也只有⼀种选择：放或者不放。我们可以定义状态矩阵：F[i, v] 表⽰前 i 件物品恰放⼊⼀个容量为 v 的背包可以获得的最⼤价值。则其状态转移⽅程便是：F[i,v]=maxF[i−1,v],F[i−1,v−Ci]+Wi简单解析⼀下上述⽅程：给定了背包容量 v 的情况下，前 i 个物品恰放⼊背包的最⼤总价值这个⼦问题只需要考虑第 i 个物品是否放⼊背包。当前物品不放⼊背包的情况下，当前总价值与前 i -1 个物品恰放⼊容量 v 的背包的总价值相等；⽽如果放⼊背包，则留给前 i-1 个物品将会减⼩，当前总价值与前 i -1 个物品恰放⼊容量 v−Ci 的背包的总价值加上当前物品价值Wi相等。**我们将”给定了背包容量 v 的情况下，前 i 个物品恰放⼊背包的最⼤总价值“这个⼦问题转化为了只和前 i-1 个物品相关的⼦问题。**同时，我们使⽤⼆维数组来存储状态矩阵 F[i, v] ，减少了重叠⼦问题带来的重复计算时间。空间复杂度优化上述问题的空间复杂度为O(VN)，时间复杂度已经达到了最优，但空间复杂度存在着优化空间。我们通过观察状态转移矩阵发现，第 i 个物品的状态往往只依赖于第 i-1 个物品的状态，那么我们可以很轻松地想到只使⽤两⾏数组存储两个时刻的状态，每次更新到 i+1 个物品时，我们让第 i 个物品的状态覆盖第 i-1 个物品的状态，同时让当前物品的状态填充第⼆⾏数组即可。这⼀⽅法叫做滚动数组法。但其实，我们可以进⼀步优化到只使⽤⼀⾏数组来表⽰状态。观察状态转移⽅程，我们发现，F[i, v] 只和F[i-1, v]与F[i-1, v-C]有关 ，即当前状态所依赖的⼦状态，其列数必然⼩于等于当前状态（v和v-c)。也就是说： 在”填写DP表“的时候，当前⾏总是参考了它上⾯⼀⾏“头顶上” 那个位置和“左上⾓”某个位置的值。因此，我们可以只开⼀个⼀维数组，从后向前依次填表即可。之所以需要从后向前更新状态，是因为我们需要使⽤到之前的状态。如果从前向后更新，原先的状态F[i-1,v]会被新状态F[i,v]覆盖掉，导致在后⾯需要使⽤F[i-1,v]时⽆法找到，从⽽出现计算错误。通过状态压缩，我们可以将空间复杂度优化为O(V)，只⽤⼀个数组F[v]解决01背包问题。空间复杂度：O(VN)时间复杂度：O(V)初始化的细节问题我们看到的求最优解的背包问题题⽬中，事实上有两种不太相同的问法。有的题⽬要求“恰好装满背包”时的最优解，有的题⽬则并没有要求必须把背包装满。⼀种区别这两种问法的实现⽅法是在初始化的时候有所不同。如果要求恰好装满背包，那么在初始化时除了 F[0] 为 0，其它 F[1…V] 均设为 −∞，这样可以保证最终得到的 F[ V ] 是⼀种恰好装满背包的最优解。如果并没有要求必须把背包装满，⽽是只希望价格尽量⼤，初始化时应该将 F[0…V ] 全部设为 0。 这是为什么呢？可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放⼊背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为 -∞ 了。如果背包并⾮必须被装满，那么任何容量的背包都有⼀个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0了。⼀个例题⼀个01背包问题的实例是：416. 分割等和⼦集这道题⽬的问题是： 给定⼀个只包含正整数的⾮空数组。是否可以将这个数组分割成两个⼦集，使得两个⼦集的元素和相等。做这道题需要做这样⼀个等价转换：是否可以从这个数组中挑选出⼀些正整数，使得这些数的和等于整个数组元素的和的⼀半。前提条件是：数组的和⼀定得是偶数，即数组的和⼀定得被 2 整除，这⼀点是特判。我们将其抽象为01背包问题：每个正整数可以看作是⼀个价值和重量相等的物品，假设存在⼀个最⼤容量为⼆分之数组元素总和的背包，是否可以挑选⼀些物品，恰好填满这个背包，也就是这些物品的价值总和等于背包最⼤容量。按照01背包问题求解的代码为：class Solution: def canPartition(self, nums: List[int]) -> bool:

c=sum(nums) if c%2!=0: return False else: c//=2 dp=[0 for _ in range(c+1)]#状态压缩 for j in range(len(dp)):#需要先初始化0号物品的情况，0号物品可以正向计算 dp[j]=nums[0] if j>=nums[0] else 0 for i in range(1,len(nums)): for j in range(len(dp)-1,nums[i]-1,-1): dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])#当前背包容量可以放⼊的最⼤价值物品（可以选取的最⼤整数和） if dp[-1]==c:#如果前i个物品恰好能填满容量为c的背包，即可选择⼀些整数，和为总元素和的⼀半 return True return False实际上，我们还可以将01背包问题在本题条件下进⼀步优化，不需要求解出实际的价值，只需要判断能否选取⼀些物品填满当前背包容量即可。class Solution: def canPartition(self, nums: List[int]) -> bool:

c=sum(nums) if c%2!=0: return False else: c//=2 dp=[0 for _ in range(c+1)] for j in range(len(dp)):#需要先初始化0号物品的情况，0号物品可以正向计算 dp[j]=True if j==nums[0] else False for i in range(1,len(nums)): for j in range(len(dp)-1,nums[i]-1,-1): dp[j]=dp[j] or dp[j-nums[i]]#选或不选当前整数的两种情况下，只要有⼀种能填满当前背包容量即可将当前状态设为True if dp[-1]:#如果dp[c]为True，则说明可以选择⼀些整数，和为总元素和的⼀半 return True return False完全背包问题题⽬有 N 件物品和⼀个容量为 V 的背包。放⼊第 i 件物品耗费的费⽤是C1i，得到的价值是Wi。每个物品有⽆限个可⽤。求解将哪些物品装⼊背包可使价值总和最⼤。基本思路完全背包问题看上去只和01背包问题有很⼩的区别，区别在于完全背包问题每种物品可选的数⽬是任意的。我们很容易想到⼀种贪⼼的思路：优先选择性价⽐较⾼的物品。但仍旧有⼀个问题，那就是同⼀种物品虽然可以选择任意多件，但仍旧只能以件为单位，也就是说单个物品是⽆法拆分的，不能选择半件，只能多选⼀件或者少选⼀件。这样就造成了⼀个问题，往往⽆法⽤性价⽐最⾼的物品来装满整个背包，⽐如背包空间为10，性价⽐最⾼的物品占⽤空间为7，那么剩下的空间该如何填充呢？你当然会想到⽤性价⽐第⼆⾼的物品填充，如果仍旧⽆法填满，那就依次⽤第三、第四性价⽐物品来填充。想要举反例很简单，⽐如只有两个物品：物品A：价值5，体积5，物品B：价值8：体积7，背包容量为10，物品B的性价⽐显然要⽐物品A⾼，那么⽤贪⼼算法必然会选择放⼊⼀个物品B，此时，剩余的空间已⽆法装下A或者B，所以得到的最⾼价值为8，⽽实际上，选择放⼊两个物品A即可得到更⾼的价值10。所以这⾥贪⼼算法并不适⽤。我们从每种物品的⾓度考虑，与它相关的策略已并⾮取或不取两种，⽽是有取 0 件、取 1 件、取 2 件……直⾄取 [V /Ci]件等许多种。 我们基于01背包问题，可以推导出它的动态规划转移公式为：不难看出，01背包问题是完全背包问题的⼀种特殊情况。由于此时需要遍历0到[V /Ci]种策略，所以需要三层枚举，总的时间复杂度为⼀个简单有效的优化是：若两件物品 i、j 满⾜ Ci ≤ Cj 且 Wi≥Wj，则将可以将物品 j 直接去掉，不⽤考虑。任何情况下都可将价值⼩费⽤⾼的 j 换成物美价廉的 i，得到的⽅案⾄少不会更差。这和贪⼼算法不⼀样，因为这⾥不仅要求性价⽐⾼，且物品的重量还需要更⼩。转化为01背包问题实际上，我们可以将完全背包问题转化为⼀个01背包问题，转化的⽅法为：将⼀种物品的不同选择次数拆成多件只能选 0 件或 1 件的 01背包中的物品。考虑到第 i 种物品最多选[V /Ci]件，于是可以把第 i 种物品转化为 [V /Ci] 件费⽤及价值均不变的物品。更进⼀步优化，我们知道，考虑到⼆进制数的性质，任意1个数都可以表⽰为若⼲个2k的组合。所以，我们只需要将物品拆分为 log[V /Ci]件物品即可。空间复杂度优化与01背包问题类似，完全背包问题的空间复杂度依然可以使⽤状态压缩进⾏空间优化。我们同样可以使⽤类似的⽅法将空间复杂度降为O(N)，它和01背包问题唯⼀的区别在于：不需要反向遍历填充DP表，正向填充即可。这是因为，01背包问题中，我们最多可以添加1个同种物品，所以我们只能在前 i-1 个物品的结果上进⾏添加，倒序遍历是防⽌这个结果被覆盖掉。⽽完全背包问题中，我们最多可以添加⽆限个物品，我们可以在前 i 个物品的结果上继续添加，⽽想要使⽤前 i 个物品的放置结果，必须正向遍历。⼀个例题⼀个完全背包问题的实例是：⾯试题 08.11. 硬币这道题的⽬的是： 给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有⼏种表⽰法。 很明显，这是⼀个完全背包问题，背包容量为n，有四种物品，我们可以将它们的价值和重量看作是相同的。这⾥我们要求的不是最⼤价值，⽽是恰好能填满背包的组合数⽬。class Solution: def waysToChange(self, n: int) -> int: dp = [0 for _ in range(n+1)] dp[0] = 1 coins = [1, 5, 10, 25] for coin in coins: for i in range(1, n+1): dp[i] += dp[i-coin] if i-coin>=0 else 0 return dp[-1] % 1000000007需要注意的是：常规完全背包问题，可以调换上述两层循环的位置，但是在这道题⾥不可以，会导致重复的组合，⽽先遍历币值可以保证结果组合的币值升序，从⽽不会重复。

2023年8月1日发(作者：)

动态规划经典问题《背包问题》，弄懂这个你就懂了动态规划背包九讲背包问题是动态规划问题中最为经典的问题之⼀，可以说完全弄明⽩了背包问题，能够很⼤程度上帮助我们了解动态规划转移⽅程的基本推导。背包问题的经典讲义为浙江⼤学崔添翼同学撰写的《背包九讲》，本⽂是我阅读该⽂章过程中的笔记和感想。动态规划的思路其实并不难想到，⼤多数问题只需要看⼀眼就能知道是否可以采⽤动规求解了，难点在于如何推导出合适的状态矩阵和状态转移⽅程。这需要我们多⼿写DP表，仔细找规律。动态规划问题基本概念动态规划⽅法要寻找符合“最优⼦结构“的状态和状态转移⽅程的定义，在找到之后，这个问题就可以以“记忆化地求解递推式”的⽅法来解决。⽽寻找到的定义，才是动态规划的本质。⼀般来说，当问题具有以下三个特点的时候，适⽤动态规划⽅法解决：最优⼦结构： ⼤问题的最优解可以由⼩问题的最优解推出⽆后效性： 如果给定某⼀阶段的状态，则在这⼀阶段以后过程的发展不受这阶段以前各段状态的影响。重叠⼦问题：相同的⼦问题可能被重复求解多次其实，上述前两个特点准确说是分治算法的特点。动态规划和递归算法本质上都是分治算法的⼀个⼦集，它们都是将⼤问题分解为⼩问题进⾏求解。⽽第三个特点区分了使⽤递归和使⽤动态规划的情况：⼀般来说，⼦问题独⽴的情况我们使⽤递归算法解决即可，⽽⼦问题重叠必须使⽤动态规划，否则时间复杂度会⼤⼤升⾼。我们以最简单的斐波那契数列为例，当求解第101项时，我们需要计算第100项和第99项，⽽当求解第102项时，我们需要求解100项和第101项。如果我们直接使⽤递归算法，那么求解第101项和第102项会重复计算第100项两次，这将⽩⽩浪费许多时间。实际上，如果我们对递归算法稍作修改，就可以让其变为动态规划的形式，即另加⼀个⽤于记忆的数据结构。这种做法叫做记忆化搜索，它本质上就是⼀种⾃顶向下的动态规划算法（从⼤问题到⼩问题）。如果我们从⼩问题开始求解，最终递推出所要求的⼤问题结果，那么这也是⼀种动态规划的实现⽅法（⾃底向上）。有不少博客都将记忆化搜索和⾃底向上的动态规划区分开来，将后者定义为动态规划，实际上我认为⼆者都是动态规划的不同实现形式。如果我们使⽤动态规划算法，它将在计算的过程中将得到的第100项的结果存储起来，从⽽避免重复计算，这也是为什么动态规划算法能够⼤⼤减少运⾏时间的原因。动态规划算法的关键点总结为：动态规划法试图只解决每个⼦问题⼀次⼀旦某个给定⼦问题的解已经算出，则将其记忆化存储，以便下次需要同⼀个⼦问题解之时直接查表。动态规划算法往往还会被拿来和贪⼼算法⽐较，但贪⼼算法只会关注局部最优解，当局部最优⽆法达到全局最优时，贪⼼算法将出错。实际上，如何选择各种策略可以总结为：每个阶段只有⼀个状态->递推；每个阶段的最优状态都是由上⼀个阶段的最优状态得到的->贪⼼；每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到⽽不管之前这个状态是如何得到的->动态规划。同时，我们也要注意，尽管动态规划具有⽆后效性，但并不代表我们不可以⽤动态规划解决求解需要获取过程组合的问题，例如：140. 单词拆分 II。0-1背包问题题⽬有 N 件物品和⼀个容量为 V 的背包。放⼊第 i 件物品耗费的费⽤是C1i，得到的价值是Wi。求解将哪些物品装⼊背包可使价值总和最⼤。基本思路最基础的背包问题，每件物品只有1个，也只有⼀种选择：放或者不放。我们可以定义状态矩阵：F[i, v] 表⽰前 i 件物品恰放⼊⼀个容量为 v 的背包可以获得的最⼤价值。则其状态转移⽅程便是：F[i,v]=maxF[i−1,v],F[i−1,v−Ci]+Wi简单解析⼀下上述⽅程：给定了背包容量 v 的情况下，前 i 个物品恰放⼊背包的最⼤总价值这个⼦问题只需要考虑第 i 个物品是否放⼊背包。当前物品不放⼊背包的情况下，当前总价值与前 i -1 个物品恰放⼊容量 v 的背包的总价值相等；⽽如果放⼊背包，则留给前 i-1 个物品将会减⼩，当前总价值与前 i -1 个物品恰放⼊容量 v−Ci 的背包的总价值加上当前物品价值Wi相等。**我们将”给定了背包容量 v 的情况下，前 i 个物品恰放⼊背包的最⼤总价值“这个⼦问题转化为了只和前 i-1 个物品相关的⼦问题。**同时，我们使⽤⼆维数组来存储状态矩阵 F[i, v] ，减少了重叠⼦问题带来的重复计算时间。空间复杂度优化上述问题的空间复杂度为O(VN)，时间复杂度已经达到了最优，但空间复杂度存在着优化空间。我们通过观察状态转移矩阵发现，第 i 个物品的状态往往只依赖于第 i-1 个物品的状态，那么我们可以很轻松地想到只使⽤两⾏数组存储两个时刻的状态，每次更新到 i+1 个物品时，我们让第 i 个物品的状态覆盖第 i-1 个物品的状态，同时让当前物品的状态填充第⼆⾏数组即可。这⼀⽅法叫做滚动数组法。但其实，我们可以进⼀步优化到只使⽤⼀⾏数组来表⽰状态。观察状态转移⽅程，我们发现，F[i, v] 只和F[i-1, v]与F[i-1, v-C]有关 ，即当前状态所依赖的⼦状态，其列数必然⼩于等于当前状态（v和v-c)。也就是说： 在”填写DP表“的时候，当前⾏总是参考了它上⾯⼀⾏“头顶上” 那个位置和“左上⾓”某个位置的值。因此，我们可以只开⼀个⼀维数组，从后向前依次填表即可。之所以需要从后向前更新状态，是因为我们需要使⽤到之前的状态。如果从前向后更新，原先的状态F[i-1,v]会被新状态F[i,v]覆盖掉，导致在后⾯需要使⽤F[i-1,v]时⽆法找到，从⽽出现计算错误。通过状态压缩，我们可以将空间复杂度优化为O(V)，只⽤⼀个数组F[v]解决01背包问题。空间复杂度：O(VN)时间复杂度：O(V)初始化的细节问题我们看到的求最优解的背包问题题⽬中，事实上有两种不太相同的问法。有的题⽬要求“恰好装满背包”时的最优解，有的题⽬则并没有要求必须把背包装满。⼀种区别这两种问法的实现⽅法是在初始化的时候有所不同。如果要求恰好装满背包，那么在初始化时除了 F[0] 为 0，其它 F[1…V] 均设为 −∞，这样可以保证最终得到的 F[ V ] 是⼀种恰好装满背包的最优解。如果并没有要求必须把背包装满，⽽是只希望价格尽量⼤，初始化时应该将 F[0…V ] 全部设为 0。 这是为什么呢？可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放⼊背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为 -∞ 了。如果背包并⾮必须被装满，那么任何容量的背包都有⼀个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0了。⼀个例题⼀个01背包问题的实例是：416. 分割等和⼦集这道题⽬的问题是： 给定⼀个只包含正整数的⾮空数组。是否可以将这个数组分割成两个⼦集，使得两个⼦集的元素和相等。做这道题需要做这样⼀个等价转换：是否可以从这个数组中挑选出⼀些正整数，使得这些数的和等于整个数组元素的和的⼀半。前提条件是：数组的和⼀定得是偶数，即数组的和⼀定得被 2 整除，这⼀点是特判。我们将其抽象为01背包问题：每个正整数可以看作是⼀个价值和重量相等的物品，假设存在⼀个最⼤容量为⼆分之数组元素总和的背包，是否可以挑选⼀些物品，恰好填满这个背包，也就是这些物品的价值总和等于背包最⼤容量。按照01背包问题求解的代码为：class Solution: def canPartition(self, nums: List[int]) -> bool:

c=sum(nums) if c%2!=0: return False else: c//=2 dp=[0 for _ in range(c+1)]#状态压缩 for j in range(len(dp)):#需要先初始化0号物品的情况，0号物品可以正向计算 dp[j]=nums[0] if j>=nums[0] else 0 for i in range(1,len(nums)): for j in range(len(dp)-1,nums[i]-1,-1): dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])#当前背包容量可以放⼊的最⼤价值物品（可以选取的最⼤整数和） if dp[-1]==c:#如果前i个物品恰好能填满容量为c的背包，即可选择⼀些整数，和为总元素和的⼀半 return True return False实际上，我们还可以将01背包问题在本题条件下进⼀步优化，不需要求解出实际的价值，只需要判断能否选取⼀些物品填满当前背包容量即可。class Solution: def canPartition(self, nums: List[int]) -> bool:

c=sum(nums) if c%2!=0: return False else: c//=2 dp=[0 for _ in range(c+1)] for j in range(len(dp)):#需要先初始化0号物品的情况，0号物品可以正向计算 dp[j]=True if j==nums[0] else False for i in range(1,len(nums)): for j in range(len(dp)-1,nums[i]-1,-1): dp[j]=dp[j] or dp[j-nums[i]]#选或不选当前整数的两种情况下，只要有⼀种能填满当前背包容量即可将当前状态设为True if dp[-1]:#如果dp[c]为True，则说明可以选择⼀些整数，和为总元素和的⼀半 return True return False完全背包问题题⽬有 N 件物品和⼀个容量为 V 的背包。放⼊第 i 件物品耗费的费⽤是C1i，得到的价值是Wi。每个物品有⽆限个可⽤。求解将哪些物品装⼊背包可使价值总和最⼤。基本思路完全背包问题看上去只和01背包问题有很⼩的区别，区别在于完全背包问题每种物品可选的数⽬是任意的。我们很容易想到⼀种贪⼼的思路：优先选择性价⽐较⾼的物品。但仍旧有⼀个问题，那就是同⼀种物品虽然可以选择任意多件，但仍旧只能以件为单位，也就是说单个物品是⽆法拆分的，不能选择半件，只能多选⼀件或者少选⼀件。这样就造成了⼀个问题，往往⽆法⽤性价⽐最⾼的物品来装满整个背包，⽐如背包空间为10，性价⽐最⾼的物品占⽤空间为7，那么剩下的空间该如何填充呢？你当然会想到⽤性价⽐第⼆⾼的物品填充，如果仍旧⽆法填满，那就依次⽤第三、第四性价⽐物品来填充。想要举反例很简单，⽐如只有两个物品：物品A：价值5，体积5，物品B：价值8：体积7，背包容量为10，物品B的性价⽐显然要⽐物品A⾼，那么⽤贪⼼算法必然会选择放⼊⼀个物品B，此时，剩余的空间已⽆法装下A或者B，所以得到的最⾼价值为8，⽽实际上，选择放⼊两个物品A即可得到更⾼的价值10。所以这⾥贪⼼算法并不适⽤。我们从每种物品的⾓度考虑，与它相关的策略已并⾮取或不取两种，⽽是有取 0 件、取 1 件、取 2 件……直⾄取 [V /Ci]件等许多种。 我们基于01背包问题，可以推导出它的动态规划转移公式为：不难看出，01背包问题是完全背包问题的⼀种特殊情况。由于此时需要遍历0到[V /Ci]种策略，所以需要三层枚举，总的时间复杂度为⼀个简单有效的优化是：若两件物品 i、j 满⾜ Ci ≤ Cj 且 Wi≥Wj，则将可以将物品 j 直接去掉，不⽤考虑。任何情况下都可将价值⼩费⽤⾼的 j 换成物美价廉的 i，得到的⽅案⾄少不会更差。这和贪⼼算法不⼀样，因为这⾥不仅要求性价⽐⾼，且物品的重量还需要更⼩。转化为01背包问题实际上，我们可以将完全背包问题转化为⼀个01背包问题，转化的⽅法为：将⼀种物品的不同选择次数拆成多件只能选 0 件或 1 件的 01背包中的物品。考虑到第 i 种物品最多选[V /Ci]件，于是可以把第 i 种物品转化为 [V /Ci] 件费⽤及价值均不变的物品。更进⼀步优化，我们知道，考虑到⼆进制数的性质，任意1个数都可以表⽰为若⼲个2k的组合。所以，我们只需要将物品拆分为 log[V /Ci]件物品即可。空间复杂度优化与01背包问题类似，完全背包问题的空间复杂度依然可以使⽤状态压缩进⾏空间优化。我们同样可以使⽤类似的⽅法将空间复杂度降为O(N)，它和01背包问题唯⼀的区别在于：不需要反向遍历填充DP表，正向填充即可。这是因为，01背包问题中，我们最多可以添加1个同种物品，所以我们只能在前 i-1 个物品的结果上进⾏添加，倒序遍历是防⽌这个结果被覆盖掉。⽽完全背包问题中，我们最多可以添加⽆限个物品，我们可以在前 i 个物品的结果上继续添加，⽽想要使⽤前 i 个物品的放置结果，必须正向遍历。⼀个例题⼀个完全背包问题的实例是：⾯试题 08.11. 硬币这道题的⽬的是： 给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有⼏种表⽰法。 很明显，这是⼀个完全背包问题，背包容量为n，有四种物品，我们可以将它们的价值和重量看作是相同的。这⾥我们要求的不是最⼤价值，⽽是恰好能填满背包的组合数⽬。class Solution: def waysToChange(self, n: int) -> int: dp = [0 for _ in range(n+1)] dp[0] = 1 coins = [1, 5, 10, 25] for coin in coins: for i in range(1, n+1): dp[i] += dp[i-coin] if i-coin>=0 else 0 return dp[-1] % 1000000007需要注意的是：常规完全背包问题，可以调换上述两层循环的位置，但是在这道题⾥不可以，会导致重复的组合，⽽先遍历币值可以保证结果组合的币值升序，从⽽不会重复。