#408. 多重背包问题 II
多重背包问题 II
多重背包问题 II
题目描述
有 种物品和一个容量是 的背包。
第 种物品最多有 件,每件体积是 ,价值是 。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输入格式
第一行两个整数 ,分别表示物品种类数量和背包容量。
接下来 行,每行三个整数 ,分别表示第 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
输入样例 1
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例 1
10
提示
本题数据规模较大,适合使用二进制优化多重背包。