CODEWITHSUNDEEP
algorithm
Pavel Gatnar
Pavel Gatnar

Reputation: 4053

Effective algorithm for finding cheapest subsets

Subject
We have a catalogue of items [{id, prodno, qty, price}] and item bundles [{id, price, items:[{prodno, qty}]}].
We have to find the cheapest subset(s) - result {price, [[{id, qty}]]}, which contains specified items - query [{prodno, qty}].
Example:

items = [
  {id:1, prodno:'A', qty:1, price:1},
  {id:2, prodno:'A', qty:5, price:3},
  {id:3, prodno:'B', qty:10, price:1}
]  
bundles = [
  {id:4, price:3, items:[
    {prodno:'A', qty:2},
    {prodno:'B', qty:5}
  ]}
]  
query = [
  {prodno:'A', qty:5},
  {prodno:'B', qty:4}
]  
result = {price:4, [
  [{id:2, qty:1},{id:3, qty:1}]
]}

We have requested 5xA and 4xB and retrieved 1 cheapest subset (giving 5xA and 10xB).

Upvotes: 2

Views: 149

Answers (2)

kajacx
kajacx

Reputation: 12939

You can solve this by finding shortest path in directed acyclic graph. The problem is, the graph would have a lot of vertices. If you don't know how to solve such graph problems, I can post some links in the comments.

To create the graph, you will need as many dimensions as are there different prodno values in the query, in this case, 2 (A and B). Each dimension will have integer value range from 0 to qty. Now you can place a vertex in each position, and your goal is to get from [0,0] to [5,4]. The vertex's coordinates represent the amounts of prodno.

To add edges take each item, for example {id:1, prodno:'A', qty:1, price:1}, and add edge from each vertex [i,j] that will go to vertex [i+1, j] with cost 1. An edge represents the option to add an item to your set to obtain a new item set.

I'm not sure how you wanted the groups to work, but I understood your example correctly, you could pay 3 to use group 4, which will add 2*prodno A and 5*prodno B to your collection. In that case, just add edge form [i,j] to [i+2,j+5] with cost 3.

Two more details: Each edge has to remember it's id, so when you find the shortest path, you can read what items or groups to use. Second, if an edge would go further than the maximum value, make it go to the maximum value instead: once you got all prodno quantity you need, you don't care how much more you will have.

However this will be quite slow for bigger inputs, since it's complexity is proportional to the product of desired quantities of all prodnos.

Upvotes: 0

shapiro yaacov
shapiro yaacov

Reputation: 2346

This is essentially a variation on the set covering problem.
If I remember correctly, the greedy algorithm works pretty well for these kind of problems, but there might be more complex algorithms out there that does better.

Upvotes: 1

Related Questions