Hello,
I was reading Heuritics text and came across an algorithm below. Finding hard to analyze it can any one help me out below...
How to analyze if I take say no. of types are 5 and each type has say 20 coins.
thanks.
Let {c1, c2...cn=1} be a set of distinct coin types where ci is an integer.
Sort coin types in decreasing order.
numOfCoin = 0;
amountRemain = M;
for (i=1; i<=n && amountRemain>0; ++i) {
j = amountRemain/ci;
numCoin += j;
amountRemain -= j*ci;
}
output numCoin;