3953: 蓝桥杯C++省赛（12）：最大价值

最大价值

题目描述：

一名种菜的农民伯伯，需要在给定的时间内完成种菜，现有种不同的蔬菜提供给农民伯伯选择，且

每种蔬菜种植花费的时间不同，每种蔬菜成熟后售卖的价值也不同。

要求：

1.在限定的总时间内进行蔬菜种植，并且种植蔬菜的种类不能超出限制的数量；

2.选择最优的种植方案使得蔬菜成熟后售卖的总价值最大（可选择不同的蔬菜种植）。

例如：

给定的总时间限制为55，种植蔬菜的种类限制为3；

3种蔬菜，种菜的花费时间及售卖价格分别为：第一种21和9，第二种20和2，第三种30和21。

最优的种植方案是选择种植第一种和第三种，两种蔬菜种植总时间30+21，未超过总时间限制55。所

种植蔬菜为两种，也未超过种类限制的3种。最大总价值为9+21=30，这个方案是最优的。

输入描述：

第一行输入两个正整数t(1 ≤ t ≤ 600)和m(1 ≤ m ≤ 50)，用一个空格隔开，t代表种菜总时间限

制，代表最多可种植蔬菜种类的限制

接下来的m行每行输入两个正整数t1（1 < t1 < 101)和p(1 < p < 101)且用一个空格隔开，t1表

示每种蔬菜种植需要花费的时间，p表示对应蔬菜成熟后售卖的价值。

输出描述：

输出一个正整数，表示选择最优的种植方案后，蔬菜成熟后售卖的最大总价值

输入样例：

55 3

21 9

20 2

30 21

输出样例：

30

第一行输入两个正整数t(1 ≤ t ≤ 600)和m(1 ≤ m ≤ 50)，用一个空格隔开，t代表种菜总时间限制，代表最多可种植蔬菜种类的限制

接下来的m行每行输入两个正整数t1（1 < t1 < 101)和p(1 < p < 101)且用一个空格隔开，t1表

示每种蔬菜种植需要花费的时间，p表示对应蔬菜成熟后售卖的价值。

55 3
21 9
20 2
30 21

30