U296083 多重背包二进制优化

假设有 $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}$

将每种物品按 $s_i$ 二进制拆分成 $log_2s_i+1$ 个物品，使每种物品拆成的物品的 $s'$ 能组合成 $1\sim s_i$ 任意一个数。例如 一种物品数量有 $10$ 个，可以把这种物品分别拆成数量为 $1,2,4,3$ 的 $4$ 个物品(这种物品单价、单个的重量不变)。拆成的 $nlog_n$ 个物品跑一遍 01背包 就可以了。 时间复杂度 $O(nVlog_2s)$，空间复杂度 $O(V+nlog_2s)$ 【请将 $dp$ 数组压缩成线性大小】。 $ 0 < n \le1000 $ $ 0< V\le2000$ $0 < v_i, s_i, w_i\le 2000$