P5484: 【基础背包入门4】开心的金明

传统题
1.000s 时间限制
128MB 内存限制
3 提交
3 解决

【题目描述】
  金明有N元买m个物品,使每件物品的价值(价值=价格*重要度)总和最大。 设第j件物品的价格为v[j],重要度为w[j]
【输入】

 

N  m(其中N<30000)表示总钱数,m<25)为希望购买物品的个数。)

从第2行到第m+1行,每行有2个非负整数

v[j]w[j]

(其中v表示该物品的价格(v<=10000)w表示该物品的重要度(1~5)

【输出】

 

输出只有一个正整数,为不超过总钱数的物品的价值总和的最大值(<100000000)。

【样例输入】复制
1000 5
800 2
400 5
300 5
400 3
200 2
【样例输出】 复制
3900

题目类型~

 

咻咻~

提交答案 状态