Pro.ID1944 Title算法设计例题：混合背包 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1944 AC144 Submit703 Ratio20.48% 时间&空间限制描述背包体积为C，给出N个物品，每个物品占用体积为Vi，价值为Wi，每个物品要么至多取1件，要么至多取Mi件（Mi > 1），要么数量无限，在所装物品总体积不超过C的前提下所装物品的价值的和的最大值是多少？ 输入多测试用例。 第一行两个数N和C（C ≤ 200000，N ≤ 200），下面N行每行三个数Vi，Wi，Mi分别表示每个物品的体积、价值与数量，Mi=1表示至多取一件，Mi>1表示至多取Mi件，Mi=-1表示数量无限。 输出Description 背包体积为C，给出N个物品，每个物品占用体积为Vi，价值为Wi，每个物品要么至多取1件，要么至多取Mi件（Mi > 1），要么数量无限，在所装物品总体积不超过C的前提下所装物品的价值的和的最大值是多少？ Input 多测试用例。 第一行两个数N和C（C ≤ 200000，N ≤ 200），下面N行每行三个数Vi，Wi，Mi分别表示每个物品的体积、价值与数量，Mi=1表示至多取一件，Mi>1表示至多取Mi件，Mi=-1表示数量无限。 Output 输出一行结果：所装物品价值的最大值。 Sample Input 2 10 Sample Output 22 Author 样例输入2 10 样例输出22 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2024-9-21 08:41 , Processed in 0.017526 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
