问题 3155 --多重背包

3155: 多重背包

题目描述

张琪曼：“魔法石矿里每种魔法石的数量看起来是足够多，但其实每种魔法石的数量是有限的。” 李旭琳：“所以我们需要改变装包策略啦。” 现有N(N≤10)种魔法石和一个容量为V（0<V<200）的背包。第i种魔法石最多有n[i]件可用，每个的价值是w[i]，占用的空间是c[i]。全部物品总数不超过50。求解将哪些魔法石装入背包可使这些物品的容量总和不超过背包容量，且价值总和最大。

输入

第一行为两个数字，即V和N。以下N行为每种物品的空间，价值和数量。

输出

最大价值总和。

样例输入输出

输入#1 复制 
8 2
2 100 4
4 100 2
输出#1 复制 
400

提示

发表题解
序号 标题 作者 发表时间 费用 订购数 操作

题目信息

提交
难度
普及+/提高-
标签
点击显示
递交数
82
已通过
52
通过率
64%
时间限制
1 秒
内存限制
64 MB
来源
收藏