开朗曲奇

文章
2
资源
0
加入时间
2年10月21天

背包问题之有依赖的背包(包含模板)

有依赖的背包最好理解的题就是NOIP的金明的预算方案,其每个物品有主件和附件,附件必须在主件已经购买了的请款下才能购买,这里牵扯到有依赖的背包的一个问题,将这些进行分组之后就有多种情况即:不能购买主件,只能购买主件,能购买主件和多个附件,这些情况组成了多个可能的情况,所以这种情况可以先将一个组当中的附件进行一次01背包得到其背包容量为0~V-w[i]时的所有可能情况,然后将整个组当成一个分组背包...