匹配买卖订单的算法

Question

我正在建立一个在线股票游戏。所有订单都是按市场价格定的。没有真正的“出价”，只有直接买卖。所以这应该更容易些。是否有解决以下问题的算法：

不同数量的订单。例如，以下的购买订单.

A指令50股

订购25股

命令C为10股

5股的D指令

订购E股5股

订购30股

有一张100股的G卖单。

我需要找到正确的组合以上购买订单的方式，获得尽可能接近100股，而不超过.

背包算法可以工作，但是随着大量用户和订单的出现，性能会很快下降。有没有更有效的方法来做到这一点？

编辑：

下面是我改进的背包算法：

static int KnapSack(int capacity, int[] weight, int itemsCount)
{
    int[,] K = new int[itemsCount + 1, capacity + 1];

    for (int i = 0; i <= itemsCount; ++i)
    {
       for (int w = 0; w <= capacity; ++w)
       {
           if (i == 0 || w == 0)
              K[i, w] = 0;
           else if (weight[i - 1] <= w)
              K[i, w] = Math.Max(weight[i - 1] + K[i - 1, w - weight[i - 1]], K[i - 1, w]);
           else
              K[i, w] = K[i - 1, w];
        }
    }

    return K[itemsCount, capacity];
}

唯一的问题是，当数字很高时，它的性能确实很差。

Answer 1

/*
    Given array prices, return max profit w/ 1 buy & 1 sell
    Ex. prices = [7,1,5,3,6,4] -> 5 (buy at $1, sell at $6)

    For each, get diff b/w that & min value before, store max

    Time: O(n)
    Space: O(1)
*/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minValue = prices[0];
        int maxDiff = 0;
        
        for (int i = 1; i < prices.size(); i++) {
            minValue = min(minValue, prices[i]);
            maxDiff = max(maxDiff, prices[i] - minValue);
        }
        
        return maxDiff;
    }
};

参考文献：https://github.com/neetcode-gh/leetcode/blob/main/cpp/neetcode_150/03_sliding_window/best_time_to_buy_and_sell_stock.cpp

Answer 2

我仍然不太清楚你在问题描述中给出的例子，对于任何背包问题，我们需要两样东西的容量和利润。在这里你刚刚提供了容量。考虑到你只需要尽可能接近100，而不用担心利润，那么它就简单多了，而且可以有多种方法来实现。一种方法是把所有比剩余容量小的更大的一个拿走。如果它们大于剩余的容量，那么就转到下一个较小的容量。时间: O(NlogN)用于排序空间: O(1)

function getMax(arr, maxCap) {
  arr.sort((a, b) => b - a);
  let index = 0;
  let cap = 0;
  while (cap !== maxCap && index < arr.length) {
    const remainingCap = maxCap - cap;
    if (remainingCap >= arr[index]) {
      cap += arr[index];
    }
    index++;
  }
}