算法识别/工程

Question

假设您有一个在白天接收订单的仓库。这些订单可以是提取产品或向仓库添加产品。在一天结束时，您会得到一份仍包含在仓库中的元素 list 。由于劳动力非常稀少，因此可能会发生订单在仓库的票务系统收到订单的当天没有得到处理的情况。因此，在一天结束时，您必须将已发出的订单与仓库的库存 list 进行匹配，以找出哪些订单已实际执行，哪些订单仍未结清。

Codewise 我一直在通过几个嵌套循环来解决这个问题，这些循环只是聚合和比较试图匹配订单的库存位置。不幸的是，这并不是真正有效的，并且对于大量的订单和头寸，由此产生的问题需要相当长的时间才能完成。

为了改进，我想确定潜在的问题。 IE。是 Set Cover、Knapsack 还是其他东西，基于问题以及它是 P 还是 NP 是否有有效的算法或至少是有效的启发式方法来解决它？

Answer 1

如前所述，我们知道您有以下信息来源:

• 仍包含在仓库中的元素的日终库存 list
• 要与上面的库存列表匹配的“已发出订单”
• 一个不为人知的“票务系统”
• 白天收到“订单”，但我们不知道它们是否或如何存储

一种解决方案是根据当前和前几天的库存列表创建哈希集，然后在迭代“已发出订单”时，将订单数量与库存集之间的差异进行比较。

时间是:

• 从未排序的(据我们所知)列表创建两个集合的时间(如果有理由关心，今天的集合可以保留以备明天重复使用，将此成本减半)- 这是 O (n) 在散列集大小中，并且

• 迭代“已发出的订单”并在库存哈希集中进行两次 O(1) 查找的时间:即 O(n)，其中 n 是订单数

  <

对我来说听起来很快。