2191: 宝典2第十一章多重背包
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:127
Solved:51
Description
【题目描述】多重背包(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