网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
多重背包
成绩 | 100 | 开启时间 | 2016年05月30日 星期一 11:35 |
折扣 | 0.8 | 折扣时间 | 2016年05月30日 星期一 11:35 |
允许迟交 | 是 | 关闭时间 | 2016年05月30日 星期一 11:35 |
输入文件 | Mbag.in | 输出文件 | Mbag.out |
【题目描述】多重背包(Mbag.cpp/c/pas)
张琪曼:“魔法石矿里每种魔法石的数量看起来是足够多,但其实每种魔法石的数量是有限的。”
李旭琳:“所以我们需要改变装包策略啦。”
现有N(N≤10)种魔法石和一个容量为V(0<V<200)的背包。第i种魔法石最多有n[i]件可用,每个占用的空间是c[i],价值是w[i]。全部物品总数不超过50。求解将哪些魔法石装入背包可使这些物品的容量总和不超过背包容量,且价值总和最大。
【输入格式】
第一行为两个数字,即V和N。以下N行为每种物品的空间,价值和数量。
【输出格式】
最大价值总和。
【输入样例】
8 2
2 100 4
4 100 2
【输出样例】
400