CODEWITHSUNDEEP
algorithm
narain
narain

Reputation: 402

Algorithmic Identification / Engineering

Suppose you have a warehouse that receives orders during the day. These order can either be withdrawals or additions of products to the warehouse. At the end of the day you get an inventory list of items still contained in the warehouse. Because the workforce is stretched quite thin it can happen that an order is not taken care of at the same day it is received in the ticket system of the warehouse. Therefore at the end of the day you have to match the issued orders against the inventory list of the warehouse to find out which ones have actually been executed and which orders are still open.

Codewise i've been solving this by several nested loops just aggregating and comparing the inventory positions trying to match the orders. Unfortunately this is not really efficient and with a large number of orders and positions the resulting problem takes quite some time to complete.

In order to improve that i want to identify the underlying problem. I.e. is it Set Cover, Knapsack or something else and based on the problem and whether it is in P or NP is there an efficient algorithm or at least an efficient heuristic to solve it?

Upvotes: 0

Views: 40

Answers (1)

Tony Delroy
Tony Delroy

Reputation: 106126

As stated, we know you have the following sources of information:

  • an end-of day inventory list of items still contained in the warehouse
  • "issued orders" which are to be matched against the inventory list above
  • a "ticket system" about which nothing is known
  • "orders" coming in during the day, but we've no idea if or how they're stored

One solution is to create hash sets from the current and previous days' inventory lists, then as you iterate "issued orders", compare the order quantity with the difference between the inventory sets.

The time for this is:

  • the time to create two sets from unsorted (as far as we know) lists (if there's reason to care, the set for today can be kept for re-use tomorrow, halving this cost) - this is O(n) in the hash set size, and

  • the time to iterate over the "issued orders" and do two O(1) look-ups in the inventory hash sets: that's O(n) where n is the number of orders

Sounds pretty fast to me.

Upvotes: 1

Related Questions