sorting - 我们有一组 N 个潜在投资

Question

我们有n个潜在投资的集合S，每一个都由一对浮点数给出（金额，估计回报）有一个总金额A要投资；我们希望选择投资以最大化该金额的回报。

请解释我如何使用 nlogn 的估计回报/金额比率来订购投资。这是使用快速排序吗？我可以计算 O(n) 中的比率，那么我如何保持一个关于哪个比率属于哪个投资的指数？

Answer 1

这不是一种背包问题吗？通常这类问题是使用动态规划来解决的。网上有几个 例子，包括StackOverflow 上的主题。