题目描述(ID:12098)
标题: 01背包之金矿模型
标签: 动态规划 背包
详情:
有一个国家,所有的国民都非常老实憨厚,某天他们在自己的国家发现了n座金矿,国王知道这个消息后非常高兴,他希望能够把这些金子都挖出来造福国民,首先他把这些金矿按照在地图上的位置从西至东进行编号,依次为1、2、3、4、5、6、7、8、9……n,然后他命令他的手下去对每一座金矿进行勘测,以便知道挖取每一座金矿需要多少人力以及每座金矿能够挖出多少金子,然后动员国民都来挖金子。但是用来挖金矿的人力有限,现在只有m个人可以参与挖金矿,国王想让这m个人去n座金矿挖金子,挖的越多越好。当然,每个金矿只能挖一次。
输入格式:
输入文件第一行有两个数,第一个是国王可用用来开采金矿的总人数m(1<=m<=1000),第二个是总共发现的金矿数n(1<=n<=100)。
输入文件的第2至n+1行每行有两个数,分别表示该金矿挖掘需要的人数和该金矿可以得到的金子数。
输出格式:
输出文件仅一个整数,表示能够得到的最大金子数。
提示: http://www.tianchai.org/thread-32-1-1.html
样例:

输入

100 5
77 92
22 22
29 87
50 46
99 90

输出

133
登录并解答