2021.6.8

本文主要是介绍2021.6.8，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. AcWing 有依赖的背包问题 https://www.acwing.com/problem/content/10/

大意：有N个物品和容量为V的背包。选择物品是有限制的，即物品的依赖的关系组成一棵树的形状。如果选择一个物品必须选择它的父节点。求不超过背包容量选择物品的最大价值。

思路：对于构成树形的问题即树形dp，采用递归的方式进行求解。因为选择某个物品必须选择它的父节点，而对于它的父节点又必须选择它父节点的父节点，这就类似于一个递归的过程。

状态表示 f[u,j] 即选择了u节点，且背包容量为 j 的方案。属性为最大值。然后就是递归求以u为根节点子树。

状态划分：如果根据选择选不选某个物品来划分每次递归枚举，这样时间和空间复杂度特别大的。所以就采用经典操作，以体积为划分方式，即根据体积将子树物品划分为0~m，共m+1类，对于每一类就算有不止一个符合的，我们只需要考虑最优的就行了。对于每个子树中划分的m+1类，这样就相当于每个子树是一个物品组，每组内有m+1个选择，变成了分组背包。因为对于所有的子树，都是在选择u节点的前提下进行的，所以体积是从 m-v[u]开始，递归子树后，要把u节点加上。对于j<v[u]的情况，因为根节点u放不进去，对于子树所有点都是放不进去的，所以清空为0。

总结：对于有依赖的背包问题，如果依赖关系不复杂的话，可以将根据依赖关系将物品绑定起来，然后看成分组背包问题，例如金明的选择方案。对于依赖关系较复杂的，根据依赖关系可以构成一棵树，可以用树形dp采用递归的方式求解。

2. ACWing 背包求最优解的方案数 https://www.acwing.com/problem/content/11/

大意：N件物品背包容量为V。每件物品只能使用一次。求解使得不超过背包容量装的物品价值之和最大时的方案数。

思路：注意和背包直接求方案数问题类以及背包求具体方案类问题区分开。对于此类问题的方案数是指确保最优解的情况下，求出能到达最优解的方案个数。

实际上对于动态规划问题我们都可以看成最短路径问题，求最优解的方案数，也就相当于求最佳路径的条数，状态转移过程中的各个状态相当于各个点。即求 (0,0) 到 (n,m) 的最佳路径条数，所以我们只需要额外开一个数组，纪录当前状态最大值时的方案数就行了。根据01背包的状态转移方程 f[i,j]=max(f[i-1,j],f[i-1,j-v]+w)。如果f[i,j]=f[i-1,j]那么g[i,j]+=g[i-1,j]。如果f[i,j]=f[i-1,j-v]+w,那么g[i,j]+=g[i-1,j-v]。如果同时等于两个那么就是都加上。

总结：背包求最有解的方案数。

这篇关于2021.6.8的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！