4
\$\begingroup\$

The problem description is:

You are given n types of coin denominations of values v(1) < v(2) < ... < v(n) (all integers). Assume v(1) = 1, so you can always make change for any amount of money C. Give an algorithm which makes change for an amount of money C with as few coins as possible. [on problem set 4]

Taken from MIT Dynamic Programming Problems

Is there a linear time solution to this problem?

#include <vector>
#include <algorithm>
#include <list>
#include <iostream>
typedef std::vector<int>::iterator monetary_finder;

/*!
 * Change System class: Responsible for
 * keeping track of value to make change for
 * and the actual monetary values of our system.
 * To avoid round off error multiply everything by
 * 100 and type cast it to an integer.
 */
class change_system
{
public:
  change_system(float money) :
    m_C(money * 100),
    m_RemainingChange(money * 100)
  {
    m_MonetaryValues.push_back(0.00 * 100);

    /* TODO -- MH Allow for other monetary systems
     * this will require a sort on the values. And
     * allowing the users to pass in a vector.
     */ 
    m_MonetaryValues.push_back(0.01 * 100);
    m_MonetaryValues.push_back(0.05 * 100);
    m_MonetaryValues.push_back(0.10 * 100);
    m_MonetaryValues.push_back(0.25 * 100);
    m_MonetaryValues.push_back(0.50 * 100);
    m_MonetaryValues.push_back(1.00 * 100);
    m_MonetaryValues.push_back(5.00 * 100);
    m_MonetaryValues.push_back(10.00 * 100);
    m_MonetaryValues.push_back(20.00 * 100);
    m_MonetaryValues.push_back(50.00 * 100);
    m_MonetaryValues.push_back(100.00 * 100);

    /*
     * Don't assume that users will give you currency values
     * in order. O(nlgn)
     */
    std::sort(m_MonetaryValues.begin(), m_MonetaryValues.end());
  }
  float money() const {return m_C;}
  float remaining_change() const {return m_RemainingChange;}
  std::vector<int> &get_m_MonetaryValue() { return m_MonetaryValues; }
  float make_change();
private:
  monetary_finder find_largest_smallest_value();
  std::vector<int> m_MonetaryValues; // v(1),v(2),...,v(n)
  float m_C;
  float m_RemainingChange;
};

/*!
 * Find the largest value just below the change
 * remaining. Binary search results in O(lg n) look up
 * complexity
 */
monetary_finder change_system::find_largest_smallest_value()
{
  /*
   * If you know that your largest currency is smaller
   * than what is remaining then just return that
   */
  if(m_MonetaryValues[m_MonetaryValues.size() - 1] < m_RemainingChange) {
    return m_MonetaryValues.end() - 1;
  }

  monetary_finder left = m_MonetaryValues.begin();
  monetary_finder right = m_MonetaryValues.end();

  unsigned int index = std::distance(left, right)/2;
  monetary_finder loc = m_MonetaryValues.begin() + index;

  /*
   * A binary search to find largest value less than
   * the remaining change
   */
  int distance = std::distance(left, right);
  while (distance > 1 && (*loc) != m_RemainingChange) {
    if ((*loc) < m_RemainingChange) {
      left = loc;
    } else if ((*loc) > m_RemainingChange) {
      right = loc;
    }
    distance = std::distance(left, right);
    index = std::distance(left, right)/2;
    loc = left + index;
  }
  /*
   * When left with two elements in the array the choice should
   * be to take the largest. But if it is larger than what is remaining
   * then take the other.
   */
  if ((*loc) != m_RemainingChange) {
    loc = std::max_element(left, right);
    if ((*loc) > m_RemainingChange) {
      loc = left;
    }
  }
  return loc;
}

/*!
 * Method that finds the exact change for the value
 * specified in the constructor of the object. This will
 * be printed to the screen.
 */
float change_system::make_change()
{
  monetary_finder find = find_largest_smallest_value();
  float largest_less_than = (*find);
  while (largest_less_than != 0) {
    while (m_RemainingChange > 0) {
      m_RemainingChange -= largest_less_than;
      if (m_RemainingChange >= 0) {
        std::cout << "You get " << (largest_less_than/100) << std::endl;
      }
    }
    if (m_RemainingChange != 0) {
      m_RemainingChange += largest_less_than;
    }
    find = find_largest_smallest_value();
    largest_less_than = (*find);
  }
  return 0.0;
}

int main (int argc, char *argv[])
{
  std::vector<int> test_value;
  test_value.push_back(6);
  test_value.push_back(8);
  test_value.push_back(11);
  test_value.push_back(12);
  test_value.push_back(13);
  test_value.push_back(16);
  test_value.push_back(19);
  test_value.push_back(21);
  test_value.push_back(22);

  for (std::vector<int>::iterator i = test_value.begin(); i < test_value.end(); ++i) {
    change_system change_for_10cents(*i);
    change_for_10cents.make_change();
    std::cout << "Is what you get back for: " << (*i) << std::endl;
  }
}

Results:

You get 5
You get 1
Is what you get back for: 6
You get 5
You get 1
You get 1
You get 1
Is what you get back for: 8
You get 10
You get 1
Is what you get back for: 11
You get 10
You get 1
You get 1
Is what you get back for: 12
You get 10
You get 1
You get 1
You get 1
Is what you get back for: 13
You get 10
You get 5
You get 1
Is what you get back for: 16
You get 10
You get 5
You get 1
You get 1
You get 1
You get 1
Is what you get back for: 19
You get 20
You get 1
Is what you get back for: 21
You get 20
You get 1
You get 1
Is what you get back for: 22
\$\endgroup\$
  • \$\begingroup\$ float are not good a representing monetary units (because of their precision (or imprecision (and thus rounding errors))). So it is best to use integers. So rather than store the value as dollars and cents $12.34 store the value as only cents 1234c \$\endgroup\$ – Martin York Apr 10 '12 at 23:51
  • \$\begingroup\$ The following quick test gives the wrong results: 6/8/11/12/13/16/19/21/22 \$\endgroup\$ – Martin York Apr 11 '12 at 0:06
  • \$\begingroup\$ Are those your currency values or are those the values you are look to produce? \$\endgroup\$ – Matthew Hoggan Apr 11 '12 at 2:57
  • \$\begingroup\$ Sorry: That is $0.06 and $0.08 and $0.11 etc The float point register on your machine is different from mine. Just run through the number $0.01 to $100.00 see if you get any anomalies. Given you are using float you will probably get some very quickly. \$\endgroup\$ – Martin York Apr 11 '12 at 16:49
1
\$\begingroup\$

Firstly, yes there are better solutions: see http://www.algorithmist.com/index.php/Coin_Change

/*!
 * Find the largest value just below the change
 * remaining. Binary search results in O(lg n) look up
 * complexity
 */
monetary_finder change_system::find_largest_smallest_value()
{

I see where largest comes in. I'm not seeing where smallest does. Why are you returning an iterator rather then the value?

  /*
   * If you know that your largest currency is smaller
   * than what is remaining then just return that
   */
  if(m_MonetaryValues[m_MonetaryValues.size() - 1] < m_RemainingChange) {
    return m_MonetaryValues.end() - 1;
  }

Dubious optimization.

  monetary_finder left = m_MonetaryValues.begin();
  monetary_finder right = m_MonetaryValues.end();

  unsigned int index = std::distance(left, right)/2;
  monetary_finder loc = m_MonetaryValues.begin() + index;

  /*
   * A binary search to find largest value less than
   * the remaining change
   */
  int distance = std::distance(left, right);
  while (distance > 1 && (*loc) != m_RemainingChange) {
    if ((*loc) < m_RemainingChange) {
      left = loc;
    } else if ((*loc) > m_RemainingChange) {
      right = loc;
    }
    distance = std::distance(left, right);
    index = std::distance(left, right)/2;
    loc = left + index;
  }

So, there's a std::lower_bound function that implements this binary search for you.

  /*
   * When left with two elements in the array the choice should
   * be to take the largest. But if it is larger than what is remaining
   * then take the other.
   */
  if ((*loc) != m_RemainingChange) {
    loc = std::max_element(left, right);
    if ((*loc) > m_RemainingChange) {
      loc = left;
    }
  }

This should really be handled in the binary search

  return loc;
}
\$\endgroup\$
  • \$\begingroup\$ "Dubious optimization" ??? Saves you time. \$\endgroup\$ – Matthew Hoggan Apr 11 '12 at 4:50
  • \$\begingroup\$ @MatthewHoggan, it doesn't save you much time, and there are much better optimizations for this problem. \$\endgroup\$ – Winston Ewert Apr 11 '12 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.