Calculating the change of a vending machine I would like to know if this function is correct (I know that it works, but I have not got enough knowledge so as to demonstrate that it is correct).


  Indication: a colleccio is defined as a vector&lt; int &gt; always of size 12, so I can represent the number of banknotes and/or coins of value 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.02, 0.01 € in positions 0..11.
  
  Example: if I want to store 5 x 50€ + 2 x 20€ + 0 x 10€ + 1 x 5€ +... et cetera, I would type: colleccio v(12); v[0]=5; v[1]=2; v[2]=0; and so on.


Pre:


No money exchange has been done before the function.
machine is a valid colleccio: it is the content of the machine (how many banknotes and/or coins has inside). 
paid is another valid colleccio but, in this case, it is what the user has paid.
possible_change is an empty colleccio.
numeric_change is a valid currency (X.XX€, two decimals, positive value). Its value is the price of the product - what the customer has paid. Its value is valid before computing the function.


Description and post: i_have_change checks if, given machine and paid, exists a possible_change to be returned to the user lately. If it is possible, in possible_change there will be a valid colleccio in which it is stored the most optimum change (that is: the less "currency" items (banknotes/coins), the better). machine should be correctly modified (it doesn't matter if it changes even though I cannot give change).

Code:


bool i_have_change (colleccio&amp; machine, const colleccio&amp; paid,
                    colleccio&amp; possible_change, double numeric_change) {
  vector&lt;double&gt; p(12); //the values of the currency are stored in p.
  p[0] = 50.; p[1]  = 20.;  p[2]  = 10.;
  p[3] =  5.; p[4]  =  2.;  p[5]  =  1.;
  p[6] = .50; p[7]  = .20;  p[8]  = .10;
  p[9] = .05; p[10] = .02; p[11]  = .01;

  //Add `paid` to `machine`
  for (int i = 0; i &lt; paid.size(); ++i)
    machine[i] += paid[i];

  //I start with `numeric_change` (&gt; 0) and I keep on subtracting all $$$
  //as much as I can (they are always &lt;= `numeric_change`)
  for (int i = 0; i &lt; machine.size() and numeric_change &gt; 0; ++i) {
    while (p[i] &lt;= numeric_change and machine[i] &gt;= 1) {
      numeric_change -= p[i];
      ++possible_change[i];
      --machine[i];
    }
  }

  //If I still have `numeric_change`, I have not physical change!
  if (numeric_change != 0) return false;

  //Else, everything is correct and I've got change.
  return true;
}
I see a number of things that may help you improve your code.  Because it makes a lot of things simpler, I'm going to assume that you and your compiler are able to handle C++11.

Post complete code

Here on Code Review, we prefer longer and more complete questions and code which is different from many of the other sister sites.  For that reason, when posting a question here for review, it's often best to include a short driver code showing the context of how your code is intended to be used.  It helps reviewers quickly understand your code and give you a better review.

Use const where practical

The std::vector p gets created and destroyed every time the function is invoked.  That's not very efficient and not at all necessary.  Instead, we can make it static so it's created once and const because it shouldn't change.  We can do that with this single line:

static const std::vector&lt;double&gt; p{ 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01 };


Don't use floating point for money

There is a problem using floating point (that is, float or double types) fto represent money values.  For example, when I tried to use your code to return €0.03 I only got €0.02.  This is a fundamental problem with using double (or any floating-point representation) for money values.  An alternative is to keep a number of cents as an integer value internally.  For more depth about floating point issues, I'd recommend the excellent article "What every computer scientist should know about floating-point arithmetic" by David Goldberg.

Simplify expressions

The code currently has these lines:

if (numeric_change != 0) return false;
return true;


We can simplify this to:

return !numeric_change;


However this is something of a problem with floating point values.  Either change the variable to use and integer type or compare to a real value smaller than your minimum change amount.  For example, you might use 0.005.  Much better would be to use integers.

Think carefully about the problem

If the vending machines contains €0.07 and I put in €50.00 for something that costs €10.00 what I would want to have happen is that I would get my €50.00 back and not the €10.00 item.  What the program seems to actually do, however, is return €0.07.  That is, I would expect that the function would return the value false (which it does), and then have possible_change identical to the paid object.  The specification you quote is not very clear on this issue, but it seems like the right behavior to me.

Putting it all together

Using these suggestions, here is what the routine becomes:

bool i_have_change (colleccio&amp; machine, const colleccio&amp; paid,
                colleccio&amp; possible_change, double numeric_change) {
    static const std::vector&lt;unsigned&gt; p{ 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };

    //Add paid to machine
    for (size_t i = 0; i &lt; paid.size(); ++i)
        machine[i] += paid[i];


    unsigned change = numeric_change * 100;
    //I start with change (&gt; 0) and I keep on substracting all $$$
    //as I can (they are always &lt;= change)
    for (size_t i = 0; i &lt; machine.size() and change &gt; 0; ++i) {
        while (p[i] &lt;= change and machine[i] &gt;= 1) {
            change -= p[i];
            ++possible_change[i];
            --machine[i];
        }
    }

    if (change) {
        // can't make change so return money
        for (size_t i = 0; i &lt; paid.size(); ++i) {
            possible_change[i] = paid[i];
        }
    } 
    //If I still have change, I have not physical change!
    return !change;
}


Test code

Since the code for colleccio objects was not given, I created my own to test the code.

#include &lt;vector&gt;
#include &lt;initializer_list&gt;
#include &lt;iostream&gt;
#include &lt;numeric&gt;

class colleccio : public std::vector&lt;int&gt;
{
public:
    colleccio(std::initializer_list&lt;int&gt; w) :
        std::vector&lt;int&gt;{w}
    {}
    colleccio() : std::vector&lt;int&gt;(12) {}
    double value() const { return std::inner_product(v.begin(), v.end(), begin(), 0)/100.0; }
    friend std::ostream&amp; operator&lt;&lt;(std::ostream&amp; out, const colleccio&amp; col) {
        out &lt;&lt; "{ ";
        for (const auto n : col)
            out &lt;&lt; n &lt;&lt; ", ";
        return out &lt;&lt; "} = " &lt;&lt; col.value();
    }
private:
    static const std::vector&lt;unsigned&gt; v;
};

const std::vector&lt;unsigned&gt; colleccio::v{ 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };


Now here is a convenience macro and test code in main.

#define SHOW(X) std::cout &lt;&lt; # X " = " &lt;&lt; (X) &lt;&lt; std::endl

int main()
{
    colleccio machine{0, 0, 0, 0, 
                      0, 0, 0, 0,
                      0, 0, 0, 7};
    colleccio paid   {1, 0, 0, 0, 
                      0, 0, 0, 0,
                      0, 0, 0, 0};
    colleccio change;
    double chg_amount{40.0};

    std::cout &lt;&lt; std::boolalpha;
    SHOW(machine);
    SHOW(paid);
    SHOW(change);
    SHOW(chg_amount);
    SHOW(i_have_change(machine, paid, change, chg_amount));
    SHOW(machine);
    SHOW(paid);
    SHOW(change);
    SHOW(chg_amount);
}


Sample output


machine = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, } = 0.07
paid = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } = 50
change = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } = 0
chg_amount = 40
i_have_change(machine, paid, change, chg_amount) = false
machine = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } = 50
paid = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } = 50
change = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } = 50
chg_amount = 40