背包动态规划复习
01背包
考虑到最多只能选取1个，反向枚举顺序满足当前决策不会影响到同一个物品的其他决策。
朴素枚举
for(int i=1;i<=n;i++) for(int j=V;j>=v[i];j--){
dp[j]=max(dp[j-v[i]]+w[i],dp[j]);
}
完全背包
正向枚举顺序满足当前决策影响到同一物品的其他决策，那么意味着可能出现重复选取。
朴素枚举
for(int i=1;i<=n;i++) for(int j=v[i];j<=V;j++){
dp[j]=max(dp[j-v[i]]+w[i],dp[j]);
}
多重背包
考虑把一个选取限制 次的物品视为 个单元物品的 01背包 枚举。
朴素枚举
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
for(int k=V;k>=v[i];k--){
dp[k]=max(dp[k-v[i]]+w[i],dp[k]);
}
}
倍增（二进制）优化
同理，当我们采用 2 的幂级数描述选取物品的选取次数时，任意的选取次数都能被已有的 2 的幂级数所表示，原理等效于把多个单元型物品进行 01背包 枚举。（注意剩余的最后一个可能不是 2 的幂级数）
for(int i=1,p=1;i<=n;i++,p=1){
while(p<=m[i]){
for(int j=V;j>=p*v[i];j--){
dp[j]=max(dp[j-p*v[i]]+p*w[i],dp[j]);
}
m[i]-=p,p<<=1;
}
if(m[i]) for(int j=V;j>=m[i]*v[i];j--){
dp[j]=max(dp[j-m[i]*v[i]]+m[i]*w[i],dp[j]);
}
}
分组背包
考虑先对于物品体积予以枚举，那么同一组内的物品仅有其一产生的贡献（或没有选取任何物品）。
朴素枚举
for(int i=1;i<=n;i++){// The ID of Set
for(int j=V;j;j--) for(int k=0;k<q[i].size();k++){//vector
if(j>=q[i][k].v) dp[j]=max(dp[j-q[i][k].v]+q[i][k].w,dp[j]);
}
}
杂题选录
洛谷0P5020 货币系统 变形完全背包
一个结论：对于当前集合 A，我们想以最少的元素的集合 B 等价 A，那么集合 B 中所有的元素都来自于集合 A。那么我们从小到大枚举集合 A 中的数，如果我们在之前枚举的数中没有得到过他，那么统计答案，每次枚举后我们都将枚举到的数进行一遍完全背包，以得到能够组成的数。
ATCoder-[ARC073B] Simple Knapsack 变形 01 背包
考虑到体积的范围很大，无法直接进行背包。但体积的波动范围很小，我们考虑新增状态帮助我们维护变形的背包状态转移，类似于统计放了多少数，与基准值相差多少作为状态。
洛谷-P1782 旅行商的背包 混合背包（多重背包 + 分组背包）
考虑对于普通的商品直接进行多重背包。此时发现变形的商品数量很少，我们暴力枚举所以出现的变形商品的可能，并且只能选取一个，那么就是分组背包。
洛谷-P1273 有线电视网 树上分组背包（存在依赖关系背包 + 分组背包）
考虑到仅子结点是客户端，我们把以当前节点选取多少个客户端作为状态，此时做法类似于分组背包。但实际上，个人认为我们考虑把贡献划分为当前子结点所有和其他兄弟子结点所有，那么类似 01背包选取物品。
洛谷-P2515 [HAOI2010]软件安装 树上背包（存在依赖关系背包 + Tarjan 缩点）
考虑到当依赖关系组成环的结构时，仅有当所有结点全部选择时，才会产生贡献。那么考虑将环进行 Tarjan 缩点，得到了一棵树，那么我们此时在树上进行 01背包的选取物品。