0
$\begingroup$

Lets there are n stores.

A customer order x items. All the stores might not have all the items from the order.

So find the store/combination of stores that can serve the order request such that the combination that contain least number of stores.

Edit:

Example: Lets say there are 4 stores. User is ordering item 1, 3, 6, 7

Store 1 sells item 1, item 6 Store 2 sells item 1, item 2, item 3, item 4, item 5 Store 3 sells item 6, 7, 8, 9, 10 Store 4 sells item 5, item 7

The combinations of stores that can fulfil the orders { 2, 3 } , { 1, 2, 4}

So optimal solution in this case is {2,3}

P.S: I was asked this question in an interview. What would be the algorithm that would fit into the problem?

$\endgroup$
4
  • 1
    $\begingroup$ I'm having a hard time understanding your problem statement. Can edit the question to formalize it mathematically? I don't understand what you mean by "the set that contain least number of stores is selected so that there are lesser number of shipments". $\endgroup$
    – D.W.
    Sep 18, 2018 at 5:25
  • $\begingroup$ I have added an example please check $\endgroup$
    – Sam
    Sep 18, 2018 at 6:32
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Sep 18, 2018 at 9:38
  • $\begingroup$ An example can help to illustrate a problem, but does not replace a complete and precise problem statement. $\endgroup$
    – Raphael
    Sep 18, 2018 at 9:39

1 Answer 1

2
$\begingroup$

Your problem is essentially the same as set cover, a classical NP-complete problem.

In set cover, we are given sets $S_1,\ldots,S_n$ together covering a universe $U$, and the problem is to find the smallest subset that still covers $U$. The only difference between this and your problem is that you want to cover some $V \subseteq U$. You can get the classic formulation by intersecting all sets with $V$.

$\endgroup$
2
  • 1
    $\begingroup$ I would assume that the customer can order more than one of each item, which makes it just harder. It's still NP-complete. $\endgroup$
    – gnasher729
    Sep 18, 2018 at 8:17
  • $\begingroup$ Here, $n$ is fixed and presumably small-ish. $\endgroup$
    – Raphael
    Sep 18, 2018 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.