getting min value based on inputs

I was wondering if this is even possible. given a list of plans... Code    Price    Minutes PLANA   $25.00   0 PLANB   $32.00   200 PLANC   $42.00   500 PLAND   $52.00   750 PLANE   $63.00   900 PLANF   $84.00   1,400 PLANG   $105.00   2,100 PLANH   $155.00   4,000 PLANI   $210.00   6,000 And given the user's input of say 10 lines and 9500 minutes. Is it possible to come up with the least costly set up that meets the requirements? For example. 10 lines 9,500 minutes would be 1 @ PLANI = 210.00 (6000 minutes) 7 @ PLANC = 294.00 (3500 minutes) 2 @ PLANA = 50.00 (0 minutes) total = 554.00 You'd think it'd be 1 @ PLANI = 210.00 (6000 minutes) 1 @ PLANG = 105.00 (2100 minutes) 1 @ PLANF = 84.00 (1400 minutes) so that satisfies the 9500 minute requirement so the other lines would have to go to PLANA 7 @ PLANA = 175.00 (0 minutes) total = 574.00 Any ideas would be most helpful!

----- Excess quoted text cut - see Original Post for more ----- This sounds like a variation of the traveling salesman problem: http://en.wikipedia.org/wiki/Travelling_salesman_problem My comp sci knowledge and math skills aren't really good enough to help you come up with the best solution to your problem, but you might take a look at the various approximation algorithms out there to find a solution. Dave Watts, CTO, Fig Leaf Software http://www.figleaf.com/ Fig Leaf Software provides the highest caliber vendor-authorized instruction at our training centers in Washington DC, Atlanta, Chicago, Baltimore, Northern Virginia, or on-site at your location. Visit http://training.figleaf.com/ for more information!

Well, there's always the brute force method. I believe it would take #plans x #lines tries to complete, but the good news multiplication and addition are very fast operations even when done millions of times. :) I don't think there is any algorithm or equation you can use since there is no real pattern or method to the different plans.   ~Brad I was wondering if this is even possible. given a list of plans...

I'd be willing to try brute force.. but how would I come up with the code to try different options? ----- Excess quoted text cut - see Original Post for more -----

On Saturday 05 Sep 2009, brad@bradwood.com wrote: > I believe it would take #plans x #lines tries to complete, but the good > news multiplication and addition are very fast operations even when done > millions of times. :) Yup, I do a brute force search, store the results, and then reporting to the user is just a lookup. Should be nice and fast. -- Helping to simultaneously establish essential designs as part of the IT team of the year, '09 and '08 **************************************************** This email is sent for and on behalf of Halliwells LLP. Halliwells LLP is a limited liability partnership registered in England and Wales under registered number OC307980 whose registered office address is at Halliwells LLP, 3 Hardman Square, Spinningfields, Manchester, M3 3EB.  A list of members is available for inspection at the registered office together with a list of those non members who are referred to as partners.  We use the word ?partner? to refer to a member of the LLP, or an employee or consultant with equivalent standing and qualifications. Regulated by the Solicitors Regulation Authority. CONFIDENTIALITY This email is intended only for the use of the addressee named above and may be confidential or legally privileged.  If you are not the addressee you must not read it and must not use any information contained in nor copy it nor inform any person other than Halliwells LLP or the addressee of its existence or contents.   If you have received this email in error please delete it and notify Halliwells LLP IT Department on 0870 365 2500. For more information about Halliwells LLP visit www.halliwells.co

We can help you come up with an algorithm, but first some questions. In your example you have a setup that proportioned an very large amount of minutes to one line and 0 minutes to 2 lines.  Is it acceptable to assign a disproportionate amount of minutes to the lines as long as they all reach the total and have the cheapest possible price? Also, what do you do if there is no combination of plans to match the exact number of minutes desired?  Do you go with the smallest amount of overage that is still the cheapest?  What if there is a deal that goes 10 minutes over the requested amount for $100, but another configuration goes 15 minutes over the requested amount for $95?  Would you give priority to the combination that matches the minutes most closely or costs less? Also, what if there aren't any plans big enough to satisfy the number of minutes with the given number of lines.  For instance, 1 line, 10,000 minutes.  With the current plans available that is impossible.  The best you can do is one PLANI, but that still leaves you 4,000 minutes short. What would you do? What do you do if multiple plans add up to the same amount of minutes at the same price.  Which option do you pick?  Just random? Thanks. ~Brad I'd be willing to try brute force.. but how would I come up with the code to try different options?

I couldn't stop thinking about this last night so I wrote a SQL solution that appears work based off some assumptions I made about the questions I posed. SQL can be handy for brute forcing since Cartesian products represent all possible combination of 2 or more vectors.  That, and SQL Server handles lots of rows easily.   It actually performs decent considering the millions of possible combination you can quickly rack up.  Let me know how you handle the scenarios I asked about and I'll show you the code for a starting point. Actually, I might just paste it in a blog entry since it's kind of messy to paste all that SQL here. ~Brad We can help you come up with an algorithm, but first some questions.

The idea is that all lines add up to the total minutes entered in any possible way because in the end they'll share the minutes. 1 line at 10,000 minutes would fail because there are no plans of that size. Priority is on cost, not so much on minutes. For example if you entered 9100 minutes and 10 lines the solution would return 9200 minutes. I'll have to get the exact plans/minutes on Tuesday to provide the solution. And if multiple options add up to the same cost then yeah, one at random would work because it meets the requirements. Thanks! ----- Excess quoted text cut - see Original Post for more -----

Ok Greg, I went ahead and just stuck the code and explanation into a blog post since it was kind of long. http://www.codersrevolution.com/index.cfm/2009/9/7/Phone-Plan-Matchup-SQL-Brute-Force-Method Keep in mind this really just one way to do it, and it might not be the best.  I also considered using some recursion to generate the possible combinations in CF, but this method was a little easier.  Use it as a starting point or don't use it at all.  :) Thanks. ~Brad The idea is that all lines add up to the total minutes entered in any possible way because in the end they'll share the minutes. 1 line at 10,000 minutes would fail because there are no plans of that size. Priority is on cost, not so much on minutes. For example if you entered 9100 minutes and 10 lines the solution would return 9200 minutes. I'll have to get the exact plans/minutes on Tuesday to provide the solution. And if multiple options add up to the same cost then yeah, one at random would work because it meets the requirements. Thanks!

Thanks brad! We use Oracle but I should be able to adapt your solution to it. I'd like to see a CF solution mainly to see the speed difference. The database solution should blow away the CF solution but I'm curious none-the-less. Maybe using your solution I can manage something like that too ----- Excess quoted text cut - see Original Post for more -----

They use it for 100+ line accounts. Umm yeah, not going to happen. Thank for your time though Brad, good solution for learning purposes. ----- Excess quoted text cut - see Original Post for more -----