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 )

Originally Posted by ManyTimes

For this particular data, the result shall be the cheapest combination:
carID: 1 2 3 4
sellerID: 1 3 1 3

I'm not the brightest knife in the socket, but if you mean for example:
"Given Car #1, then Seller ID #1 is the cheapest." True
"Given Car #2, then Seller ID #3 is the cheapest." Seller #3 doesn't sell Car #2...?
"Given Car #3, then Seller ID #1 is the cheapest." Seller #1 doesn't sell Car #3...?
"Given Car #4, then Seller ID #3 is the cheapest." Again, Seller #3 doesn't sell Car #4...
I need some clarification if you have the time. I know someone smart is likely to help you, and I want to understand it when they do. I read Grumpy's post about matrices/ multiplication and needed to take a nap until the room stopped spinning.

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...

That does look only moderately simple to program. If I were you, I wouldn't bother with step 1, step 4, etc. You've got an array of cars you want to buy, you can make an array of bool's for "have I bought from this seller yet?". The "look back and recalculate" are for-loops. It can get a bit recursive, but if you break it all into functions that's okay. So that's what I would suggest: pass the array of bool's and maybe a row of a matrix to a function, let it pick a salesman; if necessary, call the recalculate function with a start, a stop, and all the car information.

To M.Richard Tober: I am sorry. I have a mistake in the first post.

carID: 1 2 3 4
sellerID: 1 3 1 3

The sellerID is mixed up here, in the first post. It is actually 3 1 3 1, this can be "easily" viewed if you look at the cost, since cost for car #1 is 4, seller #3 sells car#1 for 4... My bad! But cboard does not allow me to edit the post after some time, so it's not my fault after all?

To tabstop:
Yes, truly can skip step 1, step4... Was just a way to go through the steps in my head... Did not actually see it myself though, thanks.
Passing the row, check the row, recalculate if necessary from start to stop. Cleared it out for me, thanks.

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.

Correct the O() to be O(cars^sellers), which gets bigger quicker. Still, you should be OK for reasonably small numbers of both.