【模板】多重背包(Bounded Knapsack)

题目描述

有 $n$ 种物品，其中第 $i$ 种物品的数量为 $a_i$，价值为 $v_i$，重量为 $w_i$。

小 Z 要选择重量不超过 $m$ 的物品放入背包，问能得到的最大价值为多少？

输入格式

第一行输入 $n,m$ 分别表示物品的种类和背包的容量。

接下来有 $n$ 行，每行 $3$ 个整数，$a_i,v_i,w_i$ 分别表示第 $i$ 种物品的数量，价值和重量。

输出格式

一行一个整数表示答案。

样例输入 #1

3 10
2 3 4
1 4 3
2 5 3

样例输出 #1

14

数据范围

对于 $20\%$ 的数据，$n\le 5，m \le 100，a_i\le 5$

对于 $50\%$ 的数据，$n\le 100，m \le 1000，a_i\le 100$

对于 $100\%$ 的数据，$n\le 100，m \le 200000，a_i\le 50000$。

保证最终的答案在 int 范围内，$w_i \le 100$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1400。

测试点分布

出处：原题链接