In this problem you are to write an empirical analysis program to determine statistically how good the greedy algorithm is with respect to the optimal DP algorithm for coin changing. To simplify our problem assume that you select randomly 5 coins who have a denomination from 1 to 100 with one of the coins being 1 cent. Make the number of coin denominations be a variable n so you can change it later. IE don't hard code 5.
For each selection you run the greedy algorithm and the DP algorithm on this problem to determine the number of coins to obtain T ( the total amount you are creating change for). If the greedy algorithm give k coins and the DP algorithm give m coins then we can calculate the percentage ( m/k * 100). For example , if m =2 and k=6 then the DP approach results in an answer that is 33.3 % of the greedy approach. The smaller the percentage then the better DP performs over greedy.
Here is pseudo code for the problem that you should implement.
n=5
AvePer = 0
for T = 100 to 500
for i=0 to 100
select n random coins which include a 1
m = CoinCtDP(T)
k = CoinCtGreedy(T)
AvePer += (m/k)
totalAve+= avePer/100;
printout totalAve/400