# More optimal "Making Change" Problem: Knapsack challenge

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
• 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 Apr 10, 2012 at 23:51 • The following quick test gives the wrong results: 6/8/11/12/13/16/19/21/22 Apr 11, 2012 at 0:06 • Are those your currency values or are those the values you are look to produce? Apr 11, 2012 at 2:57 • 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. Apr 11, 2012 at 16:49

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;
}
• "Dubious optimization" ??? Saves you time. Apr 11, 2012 at 4:50
• @MatthewHoggan, it doesn't save you much time, and there are much better optimizations for this problem. Apr 11, 2012 at 13:08