Brendan Grieve

Actually my change solves the problem in linear time related to the number of options and number of requests and not related at all to the size of the request. My brute force method previously took an exponentially higher amount of time based on the size of the request multiplied by how many items and how many options to choose from. I have 83 plan items presently, all of them providing a wide range of options (some providing multiple domains, differing mailboxes, space etc etc), and some with limitations (IE, you can only have a maximum of a certain item etc). The change of looking at one resource at a time, in reverse size order, solving it completely, then adding all the individual solutions together, then removing a few spares at the end, solves it lightning quick. For example, I've just put an estimate that has the following (All the test items here provide 4 mailboxes and cost variying amounts but are higher than just a mailbox on its own). These items are in addition to all my other items I've added back in that provide options, bringing the total plan items available to 90 to choose from: - x10000 Mailbox resources x3 Domain1 resources x1 Domain2 resources x5 Domain3 resources x10 Domain10 resources x5 Domain34 resources x55 Domain20 resource Estimate returns straight away, that the following satisfies this - x1 Domain2 Item x3 Domain1 Item x5 Domain34 Item x5 Domain3 Item x10 Domain 10 Item x55 Domain20 Item x9684 Mailbox Item If I reduce Domain2's price to twice that of the Mailbox item such that it would be cheaper to use that, it gives: - x2422 Domain2 Item x3 Domain1 Item x5 Domain34 Item x5 Domain3 Item x10 Domain 10 Item x55 Domain20 Item There does not seem to be a limit to the complexity of the request that I can perform (at least without getting silly) and as it works with nearly 100 options to choose from fast enough to be unnoticeable I'm *very* happy! Brendan

Hi imatfaal, You're right, it is fairly straight forward, especially for the human brain which see's that pattern quite quickly, but trying to write a computer function that does that work is much trickier, unless I'm missing something. For example, what if price of the .net item for example was $2 rather than $10, but all the rest of the items were the same. The total list would then be: - .Net Plan Item - Provides 1x .net resource, 4x Mailbox resource - $2 .Com Plan Item - Provides 1x .com resource, 4x Mailbox resource - $10 Mailbox Plan Item - Provides 1x Mailbox resource - $1 Now the best option would be to use lots of .Net plan items to fulfill the 1000 mailboxes (-4 for the one we are required to get to fulfill the .com requirement). You'd end up with about 200 .net resources you don't need, but it would be cheaper than even using the Mailbox plan items. Also, there are perhaps 50 different top level domains, so a full plan item list could have about 52 options to choose from (each with their own individual prices + providing differing mailbox resources). There may also be plan items that don't provide any resource that we want, though its trivial to prune them out before hand so that at a minimum all the plan item options are offering at least one resource we want. Presently my recursive function tries the following. Assuming 3 plan item options to choose from (a,b,c), it tries: - 0a 0b 0c 0a 0b 1c 0a 0b 2c ... - Till success or adding any more of C does not reduce our resources wanted 0a 1b 0c 0a 1b 1c 0a 1b 2c ... - Till success or adding any more C does not reduce our resources 0a 2b 0c ... ... 1a 0b 0c 1a 0b 1c etc If there were 50 plan items to choose from, the number gets very big. I guess my main reason for the post is in case I've missed some blinding obvious solution as I've spent too long looking at the problem that I'm too close to it. If the only solution is a recursive function then perhaps I can break that down so I don't need to test every possible combination. Brendan UPDATE: Actually something you said has sparked an idea. Perhaps if I split my tests up so I'm only testing individual resources rather than groups, I can then dispense with a recursive function and derive a value quickly. Will think on it. UPDATE2: Figured out a solution. The missing piece is that I can simply split the resources I want and work on them separately as long as I follow a golden rule: - Reduce the solution by the smallest number of resources I need at a time (since we _have_ to solve each one)So, in my example I would do the following: - Look at the smallest resources I need to solve. In this case its either the .com or the .net as I only need 1 of each. So I pick the .com. Find which plan item solves it for the cheapest price. This is straight algebra. Reduce all the other requested resources by whatever that solution provides. So it would reduce the number of mailbox resources by 4, leaving 996. Repeat till there are no resources left

Hi All, I'm busy trying to write a 'smart' billing system, but I'm getting a bit stuck with some of the maths and thought that if someone else looked at what I'm doing you may see a much easier solution. Background: - First, just a little explanation of how it works. A person has an account that is part of a 'plan'. A plan is made up of zero or more plan items (or options in the plan), and each plan item can provide 0 or more resources. What that means is that if I have the following 3 resources I am selling: - Mailbox Resource .com Domain Resource .net Domain Resource And in my plan I have the following plan items (options): - .Com Domain - $10 Provides 1 '.com Domain Resource' Provides 4 'Mailbox resource' .Net Domain - $10 Provides 1 '.net Domain Resource' Provides 4 'Mailbox resource' Mailbox - $1 Provides 1 'Mailbox resource' So, for example if I had 2 .com domains, and 9 mailboxes, the optimal 'PlanItems' that I should have is: 2x '.Com Domain' @ $10 each 1x 'Mailbox' @ $1 Total: $21 Hope that makes sense. Ultimately a Plan would have hundreds of these options, with the options costing different amounts and providing differing number of resources. What it means is that I work with resources (they are the service I actually provide), but my customer is given the 'PlanItems' which can provide several resources. In actual fact, the 'smart' part of the billing is that the customer doesn't know about the planitems. They just buy another resource, and the billing system works out the best options for them. My Estimate function works like this: - Pass in the number of resources we want in total. Ie, 9 mailbox resources, 2 .com resources It then works out the optimal (least cost) planoptions that fulfil that critera. Doesn't matter if it provides more resources than requested. I had hoped that I could simply this to some equations, but for the life of me I can't figure anything that works. What I've had to do is write a recursive function that just tries every combination of planitem in varying amounts, returning the cheapest one. That works fine if I only have a few planitems to choose from, or if the total resources I want is fairly small. Should it get large, it gets messy. For example, with just 3 planitems to choose from, if I made a request of: 1000x mailbox resources 1x .com resource 1x .net resource Then the recursive function will loop probably (1000/4)^3 (Divided by 4 as the .com and .net provide 4 mailbox resources each, so they should max at 1000/4 worst case scenario). Soooo, looking at just 3 plan items, with the above requested resources, I have the following formulas: - a = .com Plan Item b = .net Plan Item c = Mailbox Plan Item x = .com Resource y = .net Resource z = mailbox resource So: a = x + 4z b = y + 4z c = z Thus my ultimate formula is: - ma + nb + oc = a + b + 1000c IE, what valus of m,n and o provide that solution. And somehow this needs to be weighted so that a and b are both the same weight, with c being 1/10th of the weight (the price). Is there a simpler way? Or is the only option to recursively test every option? If recursive tests are the only way then I'll just work on trying to optimize it further. Thanks, Brendan