web analytics

codevs3269 混合背包

3269 混合背包
时间限制: 1 s
空间限制: 256000 KB

题目描述 Description
背包体积为V ,给出N个物品,每个物品占用体积为Vi,价值为Wi,每个物品要么至多取1件,要么至多取mi件(mi > 1) , 要么数量无限 , 在所装物品总体积不超过V的前提下所装物品的价值的和的最大值是多少?

输入描述 Input Description
第一行两个数N,V,下面N行每行三个数Vi,Wi,Mi表示每个物品的体积,价值与数量,Mi=1表示至多取一件,Mi>1表示至多取Mi件,Mi=-1表示数量无限

输出描述 Output Description
1个数Ans表示所装物品价值的最大值

样例输入 Sample Input
2 10

3 7 2

2 4 -1

样例输出 Sample Output
22

数据范围及提示 Data Size & Hint
对于100%的数据,V <= 200000 , N <= 200 分析:都用二进制拆分。转成01背包做。

Post a Comment

You must be logged in to post a comment.