问题4402--多重背包（可数背包）4402: 多重背包（可数背包）
时间限制: 1 Sec 内存限制: 512 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]题目描述
有n种物品和一个容量为v的背包。第i种物品的容量是c[i]，价值是w[i],个数是t[i]。求解将哪些物品装入背包可使这些物品不超过背包容量，且价值总和最大。
输入
第一行n，v （n<=100,v<=10000)
下面有n行，每行表示第i个物品的c[i]、w[i]、t[i]（1<=c[i],w[i]<=10000 1<=t[i]<=100)
输出
一个数，表示最大价值总和。
样例输入
(1)
3 10
3 2 4
2 4 2
6 13 2
(2)
3 10
3 8 4
2 4 2
6 13 2
样例输出
(1)
21
说明：装容量为2的装2个，用去容量4，得到价值是8,再装容量为6的1个，用去容量6，得到价值13，一共得到价值21。
(2)
24
说明：装容量为3的装3个，用去容量9，得到价值是24。
来源/分类
[提交] [状态]