0

所以我在面试的时候遇到了这个问题，无法解决。希望有人可以提出建议。问题是这样的。

想象一下，您节省了 S 数量的整数。您正在考虑购买股票。有人为您提供了 2 个 N 大小的股票购买价格数组，以及第二天的卖出价格。编写一个能够接收 S 和 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 的股票期权，然后在第二天卖出。您的函数应在此处返回 6。

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

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

4

2 回答 2

2

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

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

于 2021-01-18T16:02:39.630 回答
1

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

玉莲

于 2021-01-18T14:10:53.887 回答