-8

Overall Aim

Find the lowest possible amount of money to add to a top-up card so the balance on the card can be completely used up. Mathematically, it's sort of similar to this.

Knowns

Starting Number - the amount of money left on the card.

Set of Prices - The set of individual prices that can be deducted from the card.

Minimum Top-Up - The minimum amount you can add to your card.

The minimum increment - you can only top up in 25p increments (e.g. £5.25 not £5.10)

Background

I live in an apartment complex. There is a laundry that everyone has to use, managed by a company called Circuit. They have an extremely complicated top-up system and make thousands of pounds every year from people who move out, leaving a small amount of money on their card. I want to make an algorithm that can tell you exactly how much to add to your card to completely zero it.

The algorithm I have written can do that, but only for one 'item'. It will tell you to add enough to buy 8 low-quality washes, for example, where it might be possible to add less to buy 3 medium-quality washes and 2 drys.

I should perhaps add that this is mainly an academic exercise; for fun.

You can see my tentative implementation in C++ here: https://github.com/SilverSkyes/F__kYouCircuit/blob/master/F__kYouCircuit/main.cpp

Community
  • 1
  • 1
  • This is a algorithmic question, and shows very little work, and debugging efforts. – パスカル Mar 19 '17 at 03:47
  • 2
    @パスカル It is tagged 'algorithm'. What's wrong with it being an algorithmic question? I'm only really a beginner coder, this took me a couple of hours. There aren't any major bugs; it runs fine. I tried really hard to clearly define a genuinely difficult, academic problem. I would do more research, but I don't know what to look for. I really don't understand why everyone's downvoting me :( –  Mar 19 '17 at 04:54
  • Well, there are a number of small things that add up. It could be seen as a mathematical question more than a programming question. You link to off-site code. You haven't made any attempt to adapt the code for multiple items yourself. The actual question is vague. Some people object to code that is called "F__kYou" even with the censoring. There's a lot of text in the question but not much information. A complete re-write could save this question, but 6 downvotes and 2 close-votes will be hard to turn around. – m69's been on strike for years Mar 19 '17 at 05:04
  • @m69 Well, thank you for at least telling me what people don't like about it. Maybe I shall rewrite it a bit better in the morning :) –  Mar 19 '17 at 05:13
  • Don't worry. [C++] tag followers are notorious for downvoting (there's a lot of professionals who get annoyed by beginners' questions). [Algorithm] tag followers are more fickle; sometimes you can nerd-snipe them with an interesting problem, whatever the quality of your question. :-) – m69's been on strike for years Mar 19 '17 at 05:20

1 Answers1

1

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
Beginner
  • 5,277
  • 6
  • 34
  • 71