面试问题：最大化股票利润
Interview Question: Maximize stock profits
所以在面试的时候遇到了这个问题，一直没能解决。希望有人可以提供建议。问题是这样的。
假设您有 S 整数储蓄。您正在考虑购买股票。有人为您提供了 2 个 N 大小的股票购买价格数组，以及第二天的卖出价格。编写一个能够接受 S 和 2 个数组的算法，以及 return 您第二天能够获得的最大利润。请注意，2 个数组的长度相等。第一个数组中索引 i 处的数字表示第 i 个股票的买入价，第二个数组中索引 i 处的数字表示第 i 个股票的卖出价。
例如。 S = 10, buy_price = [4, 6, 5], sell_price = [6, 10, 7]，你的存款是10，有3个股票期权。第一个选项买价4，第二天卖价6。第二个期权次日买入价6，卖出价10。等等等等。这里的最大利润是 6，您购买成本为 4 和 6 的股票期权并在第二天卖出。你的函数应该 return 6 here.
我最初的方法是找到每只股票的 profits/cost 比率并对它们进行排序。然而，这可能不会导致最理想的股票购买。例如，对于这种情况 S = 10, buy_price = [6, 5, 5], sell_price = [12, 9, 8]，最好的选择是不要购买价格为 6 的股票，即使它具有最高的 profits/cost 比率（您剩余的 4 储蓄不能购买任何东西）但是购买其他 2 个股票期权以获得最大利润 7.
有没有人知道如何解决这个问题？谢谢！
我觉得这个问题应该可以用整数规划来解决，可以用Excel求解器设置。我觉得问题本身不能用贪心算法解决，有错请指正
玉莲
如果我们把价格看成权重，把利润看成价值，这道题就是the 0/1 knapsack problem。这个问题是弱 NP-完全的。也就是说，没有多项式时间算法作为输入大小的函数，但是通过动态规划，您可以在多项式时间内解决这个问题作为预算的函数。
因此，如果预算相当小，则可以使用动态规划方法有效地解决此问题。
所以在面试的时候遇到了这个问题，一直没能解决。希望有人可以提供建议。问题是这样的。
假设您有 S 整数储蓄。您正在考虑购买股票。有人为您提供了 2 个 N 大小的股票购买价格数组，以及第二天的卖出价格。编写一个能够接受 S 和 2 个数组的算法，以及 return 您第二天能够获得的最大利润。请注意，2 个数组的长度相等。第一个数组中索引 i 处的数字表示第 i 个股票的买入价，第二个数组中索引 i 处的数字表示第 i 个股票的卖出价。
例如。 S = 10, buy_price = [4, 6, 5], sell_price = [6, 10, 7]，你的存款是10，有3个股票期权。第一个选项买价4，第二天卖价6。第二个期权次日买入价6，卖出价10。等等等等。这里的最大利润是 6，您购买成本为 4 和 6 的股票期权并在第二天卖出。你的函数应该 return 6 here.
我最初的方法是找到每只股票的 profits/cost 比率并对它们进行排序。然而，这可能不会导致最理想的股票购买。例如，对于这种情况 S = 10, buy_price = [6, 5, 5], sell_price = [12, 9, 8]，最好的选择是不要购买价格为 6 的股票，即使它具有最高的 profits/cost 比率（您剩余的 4 储蓄不能购买任何东西）但是购买其他 2 个股票期权以获得最大利润 7.
有没有人知道如何解决这个问题？谢谢！
我觉得这个问题应该可以用整数规划来解决，可以用Excel求解器设置。我觉得问题本身不能用贪心算法解决，有错请指正
玉莲
如果我们把价格看成权重，把利润看成价值，这道题就是the 0/1 knapsack problem。这个问题是弱 NP-完全的。也就是说，没有多项式时间算法作为输入大小的函数，但是通过动态规划，您可以在多项式时间内解决这个问题作为预算的函数。
因此，如果预算相当小，则可以使用动态规划方法有效地解决此问题。