Memoization
int makeChange( const vector<int> & coins, int change)
{
int minCoins = change;
for (int i = 0; i <coins.size(); ++i)
{
if (coins[i] == change)
return 1;
for (int j = 1; j <= change / 2; ++j)
int thisCoins = makeChange(coins, j) + makeChange(coins, change - j);
if(thisCoins < minCoins)
minCoins = thisCoins;
}
return minCoins;
}
This code determines the fewest amount of coins needed to make change from the input change. Does anybody know the easiest way to rewrite this code using memoization, which is the technique that uses recursion but adds a table of solutions. Thanks for any help.
[706 byte] By [
EHump20] at [2007-11-11 10:28:30]
# 2 Re: Memoization
void makeChange(const vector<int> & coins, int maxChange, vector<int> & coinsUsed, vector<int> & lastCoin)
{
int differentCoins = coins.size();
coinsUsed.resize( maxChange + 1);
lastCoin.resize( maxChange + 1);
coinsUsed [0] = 0;
lastCoin [ 0] = 1;
for ( int cents = 1; cents <= maxChange; cents++)
{
int minCoins = cents;
int newCoin = 1;
for ( int j =0; j < differentCoins; j++)
{
if ( coins[ j ] > cents)
continue;
if ( coinsUsed [ cents - coins[ j ] ] + 1 < minCoins )
{
minCoins = coinsUsed[ cents - coins [ j ] ] + 1;
}
}
coinsUsed [ cents ] = minCoins;
lastCoin [ cents ] = newCoin;
}
}
Ok, so I got it down to this but I am not sure how to make this recursive. Anyone got any ideas?
# 3 Re: Memoization
It looks like you need some help with understanding what memoization is. It is the middleground between calculating everything on the fly and jonnin's suggestion of just having a lookup table with the results preset.
The first thing you do with this algorithm is to consult a table of previous results: have I already calculated how to most efficiently give 65 cents in change? If so, return that stored result. If not, calculate it, store that result, and return the result. That is the "semi-recursive" nature of the structure of this kind of algorithm. So: create a table with "infinity" or some other indicator that the result has not been calculated for each of the amounts from 1 to 99. Make sure your "how do I calculate best change" algorithm is as efficient as it can be [previous results which you can look up might help you here - but might not]. Then you're ready to take change requests: look up in your table - is the value something less than "infinity"? if so, return that value/combination of coins; if not, calculate those results.
The benefit to this "lazy" (calculate only if needed) approach as opposed to calculating them all and storing all results and just looking stuff up is over time ... over many requests to make change. Some amounts will occur all the time and you'll have to calculate it once and then just look it up afterward. Some change amounts will never occur and you'll then never have to calculate them.
nspils at 2007-11-11 21:00:48 >
