采访问题:最大限度地提高股票利润

Question

所以我在一次面试中遇到了这个问题，但没能解决。希望有人能给我建议。问题是这个。

假设你在整数中节省了很多钱。你在考虑买股票。有人给你提供了两个N大小的股票收购价数组，以及第二天的卖出价格。编写一个能够接受S和2数组的算法，并返回第二天你能够实现的最大利润。注意，这两个数组的长度相等。第一数组中指数i处的数字表示第一组股票的购买价格，第二阵列中索引I处的数字表示第一组股票的卖出价格。

例如：S = 10, buy_price = [4, 6, 5], sell_price = [6, 10, 7]，你的储蓄是10，有3种股票期权。第一种选择购买价格是4，第二天的售价是6。第二种选择的收购价是6，第二天的售价是10。就这样等等。这里的最大利润是6，在这里你买了4和6的股票期权，然后在第二天卖掉。您的函数应该在这里返回6。

我最初的方法是找出每只股票的利润/成本比，并对它们进行分类。然而，这可能不会导致最理想的股票购买。例如，对于本例中的S = 10, buy_price = [6, 5, 5], sell_price = [12, 9, 8]，最好的选择不是购买成本为6的股票，即使它具有最高的利润/成本比(您不能用剩余的4种储蓄购买任何东西)，而是购买其他2种股票期权，最高利润为7。

有谁知道如何解决这个问题吗？谢谢!

Answer 1

如果我们认为价格是权数，利润是价值，那么这个问题就是0/1背包问题。该问题是弱NP-complete问题。也就是说，没有多项式时间算法作为输入大小的函数，但是通过动态规划，你可以用多项式时间作为预算的函数来解决这个问题。

因此，如果预算相当小，则可以使用动态规划方法有效地解决这个问题。

Answer 2

我认为这个问题应该可以通过整数规划来解决，而整数规划可以用Excel求解器来设置。我认为这个问题本身不能用贪婪的算法解决，但如果我错了，请纠正我。

玉莲