做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 1268. -- NOIP2006:开心的金明

1268: NOIP2006:开心的金明

时间限制: 0 Sec  内存限制: 128 MB
提交: 110  解决: 82
[上一题][提交][讨论版][状态][下一题]

题目描述

金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N  元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的N  元。于是,他把每件物品规定了一个重要度,分为5  等:用整数1~5  表示,第5  等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过N  元(可以等于N  元)的前提下,使每件物品的价格与重要度的乘积的总和最大。

设第j  件物品的价格为v[j],重要度为w[j],共选中了k  件物品,编号依次为j1...jk,则所求的总和为:v[j1]*w[j1]+..+v[jk]*w[jk]

请你帮助金明设计一个满足要求的购物单.

输入

输入的第1  行,为两个正整数,用一个空格隔开:

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

从第2  行到第m+1  行,第j  行给出了编号为j1 的物品的基本数据,每行有2  个非负整数

    v  p (其中v  表示该物品的价格(v≤10000),p  表示该物品的重要度(1~5))

输出

输出只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的 最大值(< 100000000)

样例输入

1000 5
800 2
400 5
300 5
400 3
200 2

样例输出

3900

提示

NOIP2006普及组第二题

标签

[上一题][提交][讨论版][状态][下一题]