背包问题
九讲

01背包是所有背包问题的根基。题目模型十分经典：给定背包总容量，若干件物品，每件物品只能选或者不选，每个物品有对应的体积与价值，求解背包不超过容量上限时，能够装下的最大总价值。

我们定义 dp[j] 代表背包容量为 j 时，可以获取的最大价值。原始二维状态转移：

代表第 i 件物品，有两种选择：不拿这件物品，继承上一轮结果；拿这件物品，则腾出对应体积，累加物品价值。

为了压缩二维数组的内存开销，我们优化为一维滚动数组。必须逆序遍历背包容量，保证每件物品只会被选取一次，避免物品被重复选取。

for(int i = 1; i <= n; i++){
    for(int j = V; j >= w[i]; j--){
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

完全背包与01背包的唯一区别：物品可以无限次选取。

状态转移方程：

注意第二个状态来源从 dp[i-1][...] 变成了 dp[i][...]，意味着同一物品本轮已经更新的结果可以继续被利用。一维优化之后，循环只需要把容量遍历改成正向顺序。

for(int i = 1; i <= n; i++){
    for(int j = w[i]; j <= V; j++){
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

正序遍历允许重复使用当前物品，这就是01背包与完全背包最核心的代码差异。很多初学者容易混淆正序、逆序，本质就是对状态来源理解不到位。

多重背包，每件物品给定最多可以拿 s 件。

朴素写法可以把物品拆分成 s 个独立物品，直接退化成01背包，但是复杂度很高。主流优化方案是二进制拆分，把 s 拆成若干 2 的幂次，把多个相同物品打包成新物品，转化为01背包求解；更进一步还有单调队列优化，可以把复杂度压到 $O(nV)$。

二进制拆分核心思想：把数量 s 分解成 $1, 2, 4, \ldots$ 等组合，任意 $0 \sim s$ 之间的数字都可以由这些数相加得到。拆分完成之后，每一组当做一件新物品，直接跑01背包逆序循环。

分组背包将物品划分成多个组别，每一组最多只能挑选其中一件物品。

状态转移逻辑：遍历每一组，再倒序遍历背包容量，组内遍历每一个物品，做决策。

// 遍历每一个组
for(int g = 1; g <= group_cnt; g++){
    // 逆序背包容量，和01背包保持一致
    for(int j = V; j >= 0; j--){
        // 组内遍历各个物品，最多选其一
        for(auto &item : groups[g]){
            int w = item.w, v = item.v;
            if(j >= w) dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
}

分组背包的本质，就是在每组内部做一次01背包的抉择，组内多个物品互斥，只能选一个或者全部不选。

普通背包只考虑体积价值，依赖背包引入物品依赖关系：选A物品，就必须选B物品。物品之间形成树形从属关系，就演化成树形背包DP。

树形DP一般以 DFS 遍历树节点，对子树做背包合并。每一棵子树，相当于一组物品，子树内部的选择互相约束。很多树上的选择、树上选点求最大权值的题目，底层都是依赖背包、树形背包的变形。