Sam的背包问题

Blog
题目传送门
题意很简单，就不再赘述了。
题目已经很明显地提醒了背包，哪十有八九就是 $dp$ 了。

朴素背包：
$dp_{i,j,k}$ 表示考虑了前 $i$ 个物品，总重量不超过 $j$，总体积不超过 $k$ 时的最大收益。
转移：

1. 第 $i$ 个物品不选，即 $dp_{i-1,j,k}$;
2. 第 $i$ 个物品不选，即 $dp_{i-1,j-h_i,w-v_i}+w_i$.

综上，$dp_{i,j,k}=max\{dp_{i-1,j,k}, dp_{i-1,j-h_i,k-v_i}+w_i\}$.

那么，我们可以枚举 $x$，将所有的情况取 max 即可。

你会发现空间炸了，那么只要将 $j, k$ 倒叙枚举即可，此时 $dp_{j-h_i,k-v_i}$ 一定没有更新。

$ans = \max_{x=0}^H dp_{H-x,V+x}$