StepOne wrote:Thanks for the response - it does make things a lot simpler ignoring the 1000 minute bundles (or, at least, do the calculations for 500 minute bundles, then converting to 1000 at the end is trivial).
The missing piece is that the rate for International Calls is not always £2 a minute - it depends where you are calling. There could be handsets with 200 minutes of calls costing £14, so they would be better with no bundles.
I'm trying to solve this in Excel, so what I really want is s formula that tells me for 'x' minutes called at a cost of 'y' pence, how many 500 minute bundles should I buy. Another similar formula should then be able to tell me how many hundred minute bundles.
For
general problems of this type, it's basically known (or to be precise, very strongly suspected) that there is no simple formula. The branch of mathematics concerned with such problems in general is called "integer programming", and if one looks at the Wikipedia page on the subject, one rapidly comes across terms such as "NP-complete" and "NP-hard". Those terms basically say that if the general integer programming problems can be solved reasonably efficiently, such as by a simple formula, so can an enormous number of other problems that people have spent a lot of effort on, trying to find reasonably efficient solutions, without success. Those problems include (for instance) breaking all the cryptosystems used to make electronic financial transactions secure...
However, that doesn't preclude getting formula solutions to sufficiently simple integer programming problems, and your example looks sufficiently simple to me. Specifically, for your problem as originally stated, as SteelCamel has pointed out it can be reduced to asking to reduce the cost 2A+15B+50C for A 'bundles' of 1 minute, B bundles of 100 minutes and C bundles of 500 minutes to a minimum, subject to the number of minutes A+100B+500C being at least x. And as SteelCamel has also pointed out, we know that whatever the value of x, A <= 7 and B <= 3, since a purchase of 8 single minutes can have the number of minutes increased
and the cost reduced by instead buying a 100-minute bundle, and similarly for a purchase of 4 100-minute bundles by instead buying a 500-minute bundle.
That tells us that we only need to consider the 32 combinations of A and B with 0 <= A <= 7 and 0 <= B <= 3. For each of them, calculate the number of minutes x - A - 100B that we have to cover with 500-minute bundles: if it's <= 0, we need no 500-minute bundles; otherwise we need ROUNDUP((x - A - 100B)/500,0) 500-minute bundles. I.e. for each of the 32 combinations of A and B, we can calculate the minimum value of C that will cover x minutes of calls. That gives us 32 (A,B,C) candidates for the solution, (at least) one of which must be the minimum solution, so calculate the cost 2A+15B+50C for each of those 32 candidates and choose one with the lowest cost. That would certainly be feasible to calculate with a fairly simple collection of Excel formulae (and getting it down to just one formula is probably possible, though it might be a bit tricky!).
Using knowledge of the specific numbers in your problem as originally stated, we can reduce the number of candidates. Specifically, we know that the number of minutes covered by the 100-minute and 500-minute bundles is always a multiple of 100, and every multiple of 100 minutes is achievable with at least one combination of 100-minute and 500-minute bundles. Since purchases of single minutes are so uncompetitively priced compared with purchases of bundles, it's clear that there are only two reasonable ways one might cover x minutes: either buy the next multiple of 100 down using bundles and buy (x MOD 100) single minutes, or buy the next multiple of 100 up using bundles and no single minutes. Combining that with the knowledge that it's never worth buying more than 7 single minutes, we can deduce that there are at most two possibilities for the number A of single minutes we buy and the N hundred minutes we buy in bundles, calculated as follows:
a = x MOD 100
n = (x-a) / 100
First possibility is A = 0 and N = n+1
IF (a <= 7) THEN second possibility is A = a and N = n; ELSE second possibility doesn't exist
For each of those one or two possibilities, it's then a matter of how most cheaply to buy N hundreds of minutes with bundles. The answer is fairly easy because the 500-minute bundles are a simple multiple of the size of the 100-minute bundles: buy as many 500-minute bundles as one can within the constraint of buying no more than N hundreds of minutes, then if one has 400 minutes still to buy, buy another 500-minute bundle, but if one has 300 or fewer minutes still to buy, buy them as the appropriate number of 100-minute bundles. I.e. process each possibility further as follows:
b = N MOD 5
c = (N-b) / 5
IF (b = 4) THEN B = 0 and C = c+1; ELSE B = b and C = c
This gives us one or two possibilities for (A,B,C), so finish by calculating the cost 2A+15B+50C of the single possibility, or for each of the two and choosing the one with the lowest cost. Or one can do some further analysis of the entire procedure to conclude that the possibility with A = a and N = n is only the least-cost solution if there are 0, 1 or 2 'spare' hundreds over a multiple of 500 and a <= 7, or 3 such 'spare' hundreds and a <= 2, leading to the calculation:
a = x MOD 100
n = (x-a) / 100
b = n MOD 5
c = (n-b) / 5
IF ((b <= 2 AND a <= 7) OR (b = 3 AND a <= 2)) THEN A = a and B = b and C = c;
ELSE A = 0; IF (b = 4) THEN B = 0 and C = c+1; ELSE B = b+1 and C = c;
cost = 2*A + 15*B + 50*C;
(I'll leave the job of translating that into Excel formulae as an exercise for the reader!)
One can in principle do a similar analysis for more complicated problems - but very roughly speaking, either the number of possibilities your calculations have to calculate the cost of and choose the minimum from or the number of cases in your code are liable to grow very rapidly as you add extra complications such as further bundles (especially if the various bundles on offer are quite competitively priced - this particular case was quite easy to analyse because (among other reasons) the prices 200p, 15p and 10p per minute of the three options differ markedly), minutes to different countries being priced differently, etc. It's that potentially very rapid growth in the work that needs doing as the problems become more complex that makes general integer programming problems so hard in the worst case.
By the way, as your example of a handset with 200 minutes for £14 shows, adding an option which is a sufficiently good bargain compared with other options can actually reduce the complexity of the problem: basically, adding that one option effectively eliminates two existing options from consideration. So the
effective and
apparent complexities of a specific problem may be quite different...
So to sum up, for a specific problem of this type, there may well be a reasonably easy solution that one can arrive at by analysis using the specific numbers involved. But adding extra complications is liable to make the solution more difficult, possibly
much more difficult. So I'm afraid "missing pieces" may be very significant, quite possibly completely changing the solution...
Gengulphus