2076 - 环游世界之背包问题

题目描述

张老师准备环游世界,出发之前要做的最重要的事情,当然是整理自己的背包啦。张老师有一个容积为m的背包 ,有n个物品作为放入背包的待选物品 ,每样东西都有自己的价值Wi,和体积Vi ,第i个物品有Ni个 (Ni=0时表示有无限多个),请你编程帮助张老师计算,他的背包能够存入的最大价值是多少?

30%数据满足  1 <= m,n <=1000
100%数据满足  1 <=m,n <= 10000

输入

第1行有2个整数N,M,表示物品的种类和背包的容积;
第2-N+1行,每行有3个整数Vi,Wi,Pi,分别表示每个物品的体积,价值,个数。(体积<=5000,价值<=5000,个数<=1000)

输出

一个整数,表示能够存入背包的最大价值。

样例

输入

5 50 
1 1 50
2 4 3
48 49 1
1 51 1
3 3 3

输出

106
来源

动态规划 混合背包

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题