U296062 多重背包板子

假设有 $n$ 种物品和一个容量为 $V$ 的背包。 第 $i$ 种物品的体积为 $v_i$ ，价值为 $w_i$ ，可选数量为 $s_i$（即最多能够选 $s_i$ 个）。 求背包最多能装下多少物品，使他们的价值总和最大，只需要输出最大价值即可。

$n$ $V$ $v_1$ $w_1$ $s_1$ $v_2$ $w_2$ $s_2$ $\vdots$ $v_n$ $w_n$ $s_n$

$Valve_{max}$

可以令 $f(i,j)$ 表示现在考虑前 $i$ 种物品，容量为 $j$ 的背包能够获得的最大价值。则状态转移方程为： $$ f(i, j) = \max_{k=0}^{s_i}f(i-1, j-kv_i)+kw_i $$ 其中 $k$ 表示第 $i$ 种物品选择的数量。这个方程的意思是，要么不选第 $i$ 种物品，此时背包容量不变，获得的价值就是 $f(i−1,j)$ ；要么选 $k$ 个第 $i$ 种物品，此时获得的价值是 $k\times w_i$ ，背包容量减少 $k\times v_i$ ，剩下的背包容量对应的最大价值为 $f(i−1,j−kv_i)$。 最终的结果需要求解的是 $f(n,V)$，时间复杂度 $O(nVs)$ ，空间复杂度 $O(V)$（滚动数组压）。 $0 < n, V\le100$ $0 \le v_i, s_i, w_i\le 100$