华为OD机试真题- 贪心的商人

问题描述：

一位商人有 m 元钱和 n 种物品，每种物品有一个价格和对应的价值。商人可以选择购买任意数量的物品，但每种物品只能购买一次，且购买的总价不能超过 m 元。商人想要使得购买的物品总价值最大，求最大价值。

输入格式：

第一行包含两个整数 n 和 m

接下来 n 行，每行包含两个整数 vi 和 mi，表示一个物品的价值和价格。

输出格式：

输出一个整数，表示最大的总价值。

输入样例：

3 5
1 2
2 4
4 5

输出样例：

5

解题思路：

这道题目是一个典型的背包问题，但是这个背包并不是 01 背包或者完全背包，而是可以选择任意数量的物品。我们可以将物品按照单价从高到低排序，然后从单价最高的物品开始，依次购买若干个该物品，直到购买的总价超过 m 或者该物品买不下为止。然后再考虑单价次高的物品，依次购买若干个该物品，直到购买的总价超过 m 或者该物品买不下为止，以此类推，直到所有的物品都考虑完了。这样做的时间复杂度是 O(nlogn)，因为需要排序。

参考代码：