Coding is the closest thing we have to superpower !
描述
设有N种物品,每种物品有一个重量及一个价值,且每种物品有若干件。同时有一个背包,最大载重量为M,今从N种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M,而价值的和为最大。
输入
第一行:两个整数,N(物品种数,N≤500)和M(背包容量,M≤6000);
第2..N+1行:每行三个整数W_i,C_i,S_i,表示每个物品的重量、价值和能放的最大数量。(W_i \le 100 ,C_i \le 1000 ,S_i \le 10 )
输出
一行:一个数,表示能获得的最大的价值。
样例
输入
5 1000 80 20 4 40 50 9 30 50 7 40 30 6 20 20 1
输出
1040
标签