For real life currencies and notes: their values are designed in such a way that you can get the value of the next higher note using lower value notes so Solution 1 is the best one in this case. It is not always the case however for any combination of note values. Consider the case where you want to get value 9 using notes only of 7 and 3.

This algorithm handles all cases of note values and final value;

It's just a pseudocode.

Assuming your notes are ordered from highest to lowest value.

solve( v - value, ind - current note value index) {

if (v==0) SOLUTION FOUND

if (ind == max_ind) LOWEST NOTE REACHED, NO SOLUTION IN THAT BRANCH OF THE RECURSION

integer mcn = v % Notes[ind]; // max number of current notes

for (i = mcn to 0) {

use i notes of value Notes[ind]: v-=i*Notes[ind]

check if solution exist: solve(v,ind+1)

"unuse" i notes of value Notes[ind]: v+=i*Notes[ind]

}

}

Hope this helps. If you have any questions feel free to ask.

12,291,573 members (68,258 online)

Email

Password

Sign in using