[Solved] An algorithm to find the exact amount to add to a top-up a card

by


The problem you describe is actually a very difficult problem in general, since it is related to the knapsack problem. But it is only hard if you allow very large amounts of money on the card and very many different prices.

For your real world problem with very few different prices you can solve this problem by complete enumeration: say you have one fixed to-up amount c and prices p_1$, …, p_n create nested loops of depth n, like this

to_up = 0; // this will contain the number of 0.25 increases
no_p1 = 0; // this will contain the times p1 needs to be spent
...
no_pn = 0;
starting_amount = 42.0; // specify your starting amount here
WHILE (true) // to_up loop
  WHILE (true) // number of p1
     WHILE (true) // number of p2
        // ... repeat with as many different prices you have
        // now check for solution:
        IF(starting_amount - to_up * 0.25 - no_p1 * p1 - ... - no_pn * pn == 0)
        BEGIN    
           print 'found solution: ups: %1, no p1: %2, ..., no pn: %n', no_p1, ..., no_pn
           EXIT(0);
        END
        no_p2++;
     END
     no_p1++;
  END
  to_up++;
END

solved An algorithm to find the exact amount to add to a top-up a card