You're right in that this isn't a linear programming problem. Offhand, I'm pretty sure this could be solved by dynamic programming. You could probably map this problem to a ordered graph traversal problem. In fact I remember doing a similar problem with farmers and markets.
--Guillaume C.L.-- C Erler wrote: > This appears to be a nonlinear programming problem. I haven't studied > NLP, so I don't know if there are any decent algorithms for this sort > of thing. Here is a not-completely-inefficient algorithm : > > Find the best deal for the last card in your list, ignoring shipping > costs. Find the best deal for the last two cards in your list, > ignoring shipping costs. Etc. Store these cumulative costs in a list > for later reference. > > Use backtracking to try all possible buying combinations. As you go > along, keep track of the current price with shipping. Add the current > price to the list price for the remaining cards you computed earlier. > If that's worse than the best deal you've ever found so far, even > without adding shipping on to the remaining cards, you can stop trying > the rest of this branch. > > Further optimizations are possible. For instance, if you have a group > of people who sell the same card you need, but don't sell anything else > you want, you can eliminate all but the cheapest seller's card, since > shipping costs can't possibly be reduced if you switch between them. > Do this before backtracking. Perhaps you can find and prove other > optimizations. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
