U661993 疯狂的背包问题(11) - 混合背包问题

动态规划问题中的混合背包问题模板题，结合了01背包与完全背包。

有 $N$ 种物品和一个容量为 $V$ 的背包。 对于第 $i$ 种物品，有两种类型： * 如果 $s_i = -1$，则表示该物品只有 1 件（01背包） * 如果 $s_i = 0$，则表示该物品有无限件（完全背包） 每件物品的体积为 $V_i$，价值为 $W_i$。 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。

第一行有两个整数 $N$ 和 $V$，用空格隔开，分别表示物品种数和背包容积。 接下来有 $N$ 行，每行有三个整数 $V_i$、$W_i$、$S_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和类型标记。

输出一个整数，表示最大价值。

**数据范围** * $1 \leq N \leq 1000$ * $1 \leq V \leq 1000$ * $1 \leq v_i, w_i \leq 100$ * $s_i \in \{-1, 0\}$，其中 -1 表示01背包，0 表示完全背包