背包九讲（复习）和简单树上dp
树上dp：
- 利用dfs和回溯可以后序遍历整棵树，然后我们先考虑子节点的状态然后考虑父节点的状态；
- 作用适合树形关系的最优解问题，一般是后序遍历和各种背包结合；，
- 树的遍历状态转移方程分为两种，一种的在遍历子树时的性质的状态对这个节点状态的影响，一个是遍历完所有子节点以后所有子树对这个节点性质的影响；
- 子树和本该节点性质的关系分量两种一种是继承，继承某些子树的某种状态，一种是累加，累加时应该在子树没有往下遍历是记录该节点的基础信息；
- 适合解决树的最优解；
压状dp
用来解决问题类型：
复杂度：
算法思路：利用二进制中的每个位置来记录一个点的一个状态。我们有限个点的状态我们可以开个数组来记录，然后每次遍历数组来确定它的状态，这样时间复杂度很大，我们可以开个高维数组来记录每种状态，判断它是否存在，这样的空间消耗很大，所以我们利用进制来记录；
二进制运算：
Lowbit 求出最小位置的1的位置；
按位&
^可以用来记录一个一个区间内是否每个元素重复出现或者一串数中奇数次个出现的数
>>
<<
|
****取反：可以把0的位置变成1,1的位置变成0，
我们原来1记录已经存在的状态，0，代表该状态没有存在任何数，
我们~可以把0转换成1，
***用while然后用lowbit我们就可以选出所有选来需要放的位置 ；遍历所有能走的位置；
***状态dp从0枚举到2的n次方-1；dp[(1<<n)-1];
用dfs 来实现，每种状态往下继承；
***每次走可走的位置要注意&上一个最终状态可以，避免出界；
01背包和完全背包空间优化的不同，为什么倒序：
因为01背包我们每种物品只能选一个需要保留f[i-1][j-v[i]]的状态，到了完全背包商品的数量不受限了，我们可以顺序更新，因为对于状态f[j-v[i]]不论他是不是已经包含这个物品的最优解还是包含了多个的最优解我们都成立，而且不存在f[j-v[i]]最优解包含0件而f[j]的最优解包含两件的情况；因为完全背包可以看作很多很多01背包，如果它不论他要了那个数量都是逐渐增长的
多重背包的二进制优化
对于多重背包的二进制优化：如果P件物品放N件最优，将p二进制分出来的所有数和剩下一个非2进制数一定可以表示任意小于P的一个数，那么肯定在这个大小的背包可以分入小于N的所有情况都可以更新答案。我们倒过来想如果他是最优解，o1背包肯定都会取到；所以我们把一个背包拆成多个，面对复杂的背包分情况讨论就好；
依赖背包变成分组背包
对于依赖背包我们先预处理，对于每一组来说我们有很多种策略来取主件和附件，所以我们改变思路，先对每个主件进行分组，然后每个价值对应一种策略，就变成了分组背包，这个适用于附件很多但是容量有限的情况，每个状态可能对应多种最优解，不过没关系，那么物品的个数就有V-c[i]+1个；
在dp时
对于主要物件，我们01，
For(i主件，1；n)
For(j,v,c[i])
If（能更新）
{
Dp=max();
J1=j-c[i]
For(int k=j1,k>0;k++)
Dp[j]=max(dp[j1-k]+v[i]+Dp[i][k],dp[j]);
用之前01背包的值更新dp[j]
}
背包的问题都可以转换成01背包，在有条件的背包我们先考虑那个物品取不取然后对这个价值进行01背包，复杂度在v的三方；
泛化背包：
思想逐一合并，复杂度NVV，较高，但是可以解决所有有条件的背包，问题即使是树上的dp，我们只要将每一个子节点和父节点泛化，递归调用的根节点就是答案；
最优方案的单跳路径问题，我们开一个G【i】【v】用来记录对于价值V是否要用第一个物品优化的结果，如果更新为1不更新说明f[i-1][v]=f[i][v],则直接过；
对于按字典序输出结果：
利用背包中的回溯法：
我们先按字典序将物品从小到大排序好，那么对于最优解来说如果能选前面的一定选前面的物品，正常来说我们是正序dp就无法判断最后一件是否需要，我们倒过来dp，先放字典序最大 的然后放入最小的，同时用一个G数组记录每种状态是否包含了这个物品，我们可以倒序往上找答案：
对于状态转移方程我们发现有三种分别代表不同的意思：
F[i][v]=f[i-1][v],这件物品不放解的状态最优，
F[i][v]=f[i-1][v-c[i]]+w[i],这件物品放了是才是最优方案最优解；
有一种特列，f[i-1][v-c[i]]+w[i] =f[i-1][v],代表这件物品放不放不影响结果。根据字典序最小的原则一定选就可以求出优解，我们只要倒退状态就可以了；
最优解方案数或者输出所有方案
对于输出方案总数，我们觉得只要用递归dfs倒退所有情况，如果可放可不放，则分情况递归下去，然后递归的终点是N=0,V=0; ans++;
输出所有的方案数量，我们对状态转移方程进一步理解，
如果dp[i][j]=d[i-1][j]||dp[i-1][j]==dp[i-1][j-v[i]]+w[i],则说明这是这个点的状态是在原来的背包继承过来的，相当于就是原来的两个状态的背包，所有方案数也是一脉传承下来，方案数不会变多；
如果 d[i-1][j] ==dp[i-1][j-v[i]]+w[i]，说明这个物品可有可无，因为他的方案数就是上两个方案数之和，有点像爬楼梯；
我们考虑物品次序对答案的影响，不论先考虑那个物品我们都是在选择最优策略，如果他是最优策略必然包含了所有所有物品；
我们开一个新的数组G[N][N],同时呢，那么我们只要开一维得到dp数组，其他信息用G去记录；
For I 1àN
For j 0ßV
if(j<v[i])
G[i][j]=G[i-1][j];
Else
If(dp[i-1][j]==dp[i-1][j-v[i]]+w[i])
G=
Else If(<) G=
Else
我们要考虑初始化我们将边界初始化为1代表以一个
G[1][i] (I F 1àV) =1;
网络详解：
最优方案总数这里指物品总价值最大的方案数。
我们设G[i][j]代表F[i][j]的方案总数，那么最总结果应该是G[N][V]。我们初始化G[][]为1，因为对每个F[i][j]至少应该有一种方案，即前i件物品中选取若干件物品放入剩余空间为j的背包使其价值最大的方案数至少为1，因为F[i][j]一定存在。
下面开始分析怎么求G[i][j]。对于01背包来说：
如果F[i][j]=F[i-1][j]且F[i][j]!=F[i-1][j-C[i]]+W[i]说明在状态[i][j]时只有前i-1件物品的放入才会使价值最大，所以第i件物品不放入，那么到状态[i][j]的方案数应该等于[i-1][j]状态的方案数即G[i][j]=G[i-1][j]；
如果F[i][j]=F[i-1][j-C[i]]+W[i] 且F[i][j]!=F[i-1][j]说明在状态[i][j]时只有第i件物品的加入才会使总价值最大，那么方案数应该等于[i-1][j-C[i]]的方案数，即G[i][j]=G[i-1][j-C[i]]；
如果F[i][j]=F[i-1][j-C[i]]+W[i] 且F[i][j]=F[i-1][j]则说明即可以通过状态[i-1][j]在不加入第i件物品情况下到达状态[i][j]，又可以通过状态[i-1][j-C[i]]在加入第i件物品的情况下到达状态[i][j]，并且这两种情况都使得价值最大且这两种情况是互斥的，所以方案总数为G[i][j]=G[i-1][j-C[i]]+ G[i-1][j]。
对于背包的变形，我们需要理解这里j和i的含义，并尝试试着去改变J的含义就可以了解基础的dp，例如如果要求正好所有空间都消耗的最大价值，这里的j改成正好消耗j 的最优解，所以我们对于没见物品的状态转移方程：
我们先把上种状态继承下来：
Dp[i][j]=dp[i-1][j];
然后考虑我们加入一道菜之前是否有节有的话我们可以继承；
那么正好消耗的最优解就是不放这个物品的最优解
Else (j>v[i]&&dp[i-1][j-v[i])!=0]代表有办法把前j-v[i]的价格用了
Dp=max()
如果最优解求方案数，那么每种肯定可以由原来的状态继承过来，我们只要考虑加入这个物品所增加的方案数目就好；
我们先把上种状态继承下来：
Dp[i][j]=dp[i-1][j];
G[i][j]=G[i-1][j];
然后考虑我们加入一道菜之前是否有节有的话我们可以继承；
那么正好消耗的最优解就是不放这个物品的最优解
Else (j>v[i]&&dp[i-1][j-v[i])!=0]代表有办法把前j-v[i]的价格用了
Dp=max()
If(需要更新那么就成)
G= ；
Else if(更不更新都一样)
G= + ；
G成立的前提是Dp[N][V]！=0；
初始的每种线性状态为1；
实际上呢，我觉得这里改成0，是可以的，因为代表没有一种方案可行，当j==v[i],而且能更新方案数+1；其他照常分析；
如果不要求最优解只要方案数，那么
If（j==v[i]） dp[i][j]+=1;
If(j>v[i]) dp[][]=dp[][]+dp[][];
单纯走楼梯；
对于第k优解的问题，
我们可以重最优解的想法出手，对于dp[i][j]他是从dp[i-1][j]或者dp[i-1][j-v[i]]+w[i],选了一个最优解，如果我们要求次优解，不妨设两个dp数组，一个代表最优解一个代表次优解，每个状态转移的路径不变，但是每个节点就含有了两个信息就是最优解和次优解，我们从这四个数中挑出两个作为最优解和次优解；
对于k优解，我们也可以这么考虑，只不过我们是从两个有序队列里面选择前K个；
我们来考虑初始化问题对于前第一次的前K优解我们是从两个0队列 变来实际上，所有情况都是一种策略不论是最优解还是次优解，所以我们要加个限制我们可行的方案数是dp[i][j-v[i]]中到第一个非零元素，包括这个元素，就可以避免他全部是有这种状态转换过来的最优解；所以每次我们要加个程序去check判断有效数位；
对于恰好背包的另一种解释我们知道在状态转移时，有些转移是不成立的，例如dp[i-1][j-v[i]]的值为0,所以我们转移的时候要跳过，我们不妨初始化为一个很大的负数，照常转移，然后再dp[0][0]=0,这样所有数都只有从这个点开始才可以组成最优解；
只要初始化第一行；
所以类似的，我们运用到K有接上去，将所有不可能的传承依旧传承不过不可能就是负无穷；
我们对dp[0][j] j from 1àv; 最优解为0；其他都是负无穷；
解决了这个问题
Views: 62