Thread: Algorithm, getting the lowest/cheapest combination out of some "complex data"

Hello!

For sake of the example, there are sellers who sells cars, where each car has its own price from different seller. A seller also has an additional service price which will always be added for the sellers when a customer buys a car, but is only added once.

The data:

Code:

             SellerID            1       2            3
CarID      1                    5$       9$          4$
           2                    1$       2$          -
           3                    -        2$          1$
           4                    3$       -           -
                                 +       +           +
ServiceCost                      5$     15$          9$

The values $ are cost of car ID from the seller with the ID (in red)...

This data, matrix, is not static. Service cost is always a value for a seller, it can be 0, but it is always calculated with the price, but only once, even if a buyer purchases/orders 10 cars from 1 seller. Values with a - equals a car that this particular seller does not sell.

For this particular data, the result shall be the cheapest combination:
carID: 1 2 3 4
sellerID: 1 3 1 3
costChosen: 4$ + 1$ + 1$ + 3$
serviceCost: 5$ 9$ 0$ 0$
//Service has already been added for this seller, hence 0$, because car #1 and #3 are sold from same seller, service-cost can only be added once per order of cars. Same with car#2 and #4...
So this would be a totalsum of service-cost (5+9) plus costs of the cars (4+1+1+3) = 23$

It looks like it is "just getting the minimum" at each row, then add the service-cost at the end, but it is not that easy, at all.

For simplicity's sake in this example: carID and sellerID always starts at 0 or 1 and increases by +1. It is just an index from an array of a class-object (Oh really?)...

What I have got so far you ask? Oh, that ain't much, tried solving it without recursion, ended up with loads of loops and if-else-statements...

Any suggestions?
(Bringing up some code later, recursion or maybe not..., so... brb tomorrow )

You're almost there, but then again not.

>>"Given Car #1, then Seller ID #1 is the cheapest." True
Almost, take the service-cost into consideration if a seller gets picked (is the cheapest, unless the seller has already sold a car within this "order", then do not take service-cost into consideration).
Ehm....

Code:

             SellerID            1       2            3
CarID      1                    5$       9$          4$
           2                    1$       2$          -
           3                    -        2$          1$
           4                    3$       -           -
                                 +       +           +
ServiceCost                      5$     15$          9$

Trying to clarify:
Step 1: Given Car #1 the Seller #3 is the cheapest ( 4 is less than 5)
Step 2: Service cost consideration for Seller #1 (5+5) vs Seller #3 (4+9).
Step 3: Cheapest seller for car #1 is Seller #1 (10 vs 13)

Step 4: Given Car#2 , seller #1 is cheapest ( 1 is less than 2)
Step 5: Service cost consideration for Seller #1 (1+0) vs Seller #2 (2+15)
//Note: Why 1+0 For seller 1 (Cost + service-cost)? Seller #1's service-cost has been added at Car #1, so we shall not add it again.
Step 6: Cheapest seller for car #2 is Seller #1 (1 vs 17)

Step 7: Given Car #3 , Seller #2 (2+ 15) vs Seller #3 (1+9)
Step 8: Cheapest seller for car #3 is Seller #3 (17 vs 10)

Step 9: Go back through cars sold by Seller #3 that has been checked, and recalculate (because he needs to deliver this car as far as we know, at the moment). Now Seller #3's service cost does not need to be added, because it is added here at Car #3, because only Seller #3 can sell this car.
Step 10: Given Car #1, Seller #1 was cheapest. Seller #1 (5) vs Seller #3 (4)
Step 11: Cheapest new seller for Car#1 is Seller #3

Step 11: Seller #1 has changed, take into consideration of cars between Car #1 and current state (Car #3), which mean; check car #2 again, add now Seller #1's service cost to the calculation
Step 12: Given car #2 again, if Seller #1 ( 1 + 5 ) is still less than Seller #2 (2+15), do nothing,
Step 13: Seller #1 remains the cheapest for car #2.

Step 15: Given Car #4, only Seller #1 sells this car.
Step 16: Cheapest seller for car #4 is Seller #1 (3 +0 vs null)
//3 + 0, because Car #2 is sold from Seller #1, so do not add service cost again. Vs null, cause there are no other sellers who sells car #4.

In short we end up with these for the four cars:
Step 11: Cheapest new seller for Car#1 is Seller #3
Step 13: Seller #1 remains the cheapest for car #2.
Step 8: Cheapest seller for car #3 is Seller #3
Step 16: Cheapest seller for car #4 is Seller #1

Car #1 is sold from Seller 3 for the cost: 4$
Car #2 is sold from Seller 1 for the cost: 1$
Car #3 is sold from Seller 3 for the cost: 1$
Car #4 is sold from Seller 1 for the cost: 3$

Which leaves us with a total sum of : 4+1+1+3 = 9
Add service cost for chosen sellers to total sum : 9 + 5 + 9 = 23.


There, brilliant.
You would think after actually manage to write down how the procedure shall go (somewhat), step by step, it should be the simplest thing to programme? Oh...

Assuming I'm not restating what everyone else has said, forget the idea of calculating car-by-car. Instead, calculate the cost all of the possible combinations of transactions and keep the lowest.

You'll need a function which, given an array of seller ids returns a cost. Loop through each entry in the array and add that seller's car value to the total. Also flag that the particular seller has been used. At the end, loop through the array of flags and add the service cost for each seller seen. Return the cost. Return an impossibly high cost or some other error if you hit a case where the car isn't available from a given seller.

Then use another function which generates all permutations of a N-entry string, each entry going from 0->cars-1. For example, with 4 sellers :

0000 - everything from seller 0
0001 - everything except the last from seller 0, the last from seller 1
0002 - and so on...
0003 - and so on....
0010 - you get the point...

A top level call to this would just pass in the number of sellers, cars and a pointer to the array (vector, map, whatever) holding the seller/cost matrix. Or you could get the number of sellers & cars from the size of the array if you used STL containers. Works either way. You'd get back an array which had the seller ID for each car along with maybe a total price, depending on what you need to display.

This is O(sellers * cars ^ 2) I think, so it'll get large quickly. But if you're not using too many of either it'll be fine. If the matrix is sparse (i.e. lots of entries are "this car isn't available from this seller") you can get tricky and prune out lots of the search space pretty quickly. But wait until you know there's a problem before you mess with that. The initial implementation should be pretty straightforward.

Oh - since this is C++, where I say function, think class & associated methods.