tag:blogger.com,1999:blog-6288862798546085706.post2240191266494194307..comments2021-03-08T01:00:38.190-05:00Comments on Econometrics By Simulation: Estimating Required CoinageFrancishttp://www.blogger.com/profile/16658586705916884436noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6288862798546085706.post-37537323804364063082014-07-10T08:29:07.534-04:002014-07-10T08:29:07.534-04:00Thanks for the qualifier and the original comment!...Thanks for the qualifier and the original comment!Francishttps://www.blogger.com/profile/16658586705916884436noreply@blogger.comtag:blogger.com,1999:blog-6288862798546085706.post-79652895021710548232014-07-09T09:57:55.175-04:002014-07-09T09:57:55.175-04:00Francis,
it was not my intent to prove anything w...Francis,<br /><br />it was not my intent to prove anything was wrong with your simulation or the changer function. But as you write in the intro there are cases where your algorithm doesn't work. And my thought was that DP will work in this case. And so i coded it.<br /><br />I find it interesting that your algorithm works for all possible values.<br /><br />here is new challenge - for which denominations your changer will always give the correct answer. for example c(30,25,10,5,1) is not correct all the time but c(25,10,5,1) is.<br /><br />keep up your good work on this blog<br /><br />cheers<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6288862798546085706.post-36893737369154289512014-07-08T06:30:32.440-04:002014-07-08T06:30:32.440-04:00Dear Commenter,
I am very happy that you have wri...Dear Commenter,<br /><br />I am very happy that you have written this lengthy response to my original post. In my post I stated that I was not sure if my procedure would work for all coin value options but that I was sure it would work for the common ones. I am still sure but even more so after your response. The reason is because using DP as you have has produced identical results to my original code.<br /><br /># Summing by currency choice, simple selection algorithm<br />(sumcur <- apply(curcount, 2, sum))<br /> 200 100 25 10 5 1 <br /> 400 200 750 400 200 1000<br /><br /># DP algorithm you present<br />print(apply(change.mat,2,sum))<br /> 200 100 25 10 5 1 <br /> 400 200 750 400 200 1000 <br /><br />As you can see the more rigorous model (DP) has produced the same results. I commend you on your diligence however I think it is worth thinking things through a bit more before throwing the toolbox at every problem that comes your way. <br /><br />If my algorithm had failed to produce optimal results I should think that you would easily have been able to provide a counter example for a change value in which using smaller change would be better than always going with the largest available.<br /><br />Failing to do this simpler task, I chose to stop there before spending my time conceptualizing a more complex procedure. <br /><br />Cheers,<br />FrancisFrancishttps://www.blogger.com/profile/16658586705916884436noreply@blogger.comtag:blogger.com,1999:blog-6288862798546085706.post-3602821842361009432014-07-06T10:28:46.991-04:002014-07-06T10:28:46.991-04:00i realize you like to simulate things BUT sometime...i realize you like to simulate things BUT sometimes it is not the right thing to do.<br /><br />in this case your changer function doesn't produce the correct exact change for all case. <br /><br />this is a prime example of where to use dynamic programing (DP).<br /><br />here is a short code to demonstrate<br />(sorry it is text format)<br /><br />note that your results are larger than DP gives it would be nice to see where it is different<br /><br /><br />rm(list=ls())<br />### how many coins make exact change?<br />###<br /><br /><br />### input 1, available denominations<br />### exact change for values up to n.values (input 2)<br />### output is a matrix<br />### nrows = number of values<br />### ncolumns = number of denominations<br />### e.g. mat[45,3] is how many coins of value denomination[3] <br />### are needed to make 45<br /><br />find.exact.change <- function(n.values,denominations) {<br /> n.dens <- length(denominations)<br /> <br /> exactCoin <- matrix(-1,nrow=n.values,ncol=n.dens)<br /> colnames(exactCoin) <- denominations<br /> ### loop over all possible values<br /> <br /> for (i.value in 1:n.values) {<br /> ## the maximum possible number of coins <br /> n.coins <- i.value/min(denominations) + 1<br /> n.coins.now <- n.coins<br /> v.coins <- exactCoin[i.value,]<br /> ## we are going to search what happens when you <br /> ## use given denomination and then <br /> ## look-up the remaining value (in the lookup table)<br /> <br /> for (i.denom in denominations) {<br /> new.value <- i.value - i.denom <br /> ### look up whaat change is needed for the 'new.value'<br /> if (new.value > 0) {<br /> ## change for the reminder<br /> v.coins.now <- exactCoin[new.value,]<br /> ## plus the new coin<br /> v.coins.now[as.character(i.denom)] <- 1 + v.coins.now[as.character(i.denom)]<br /> ## number of coins needed is<br /> n.coins.now <- sum(v.coins.now)<br /> }<br /> ### if this denomination gives exact change report it<br /> if (new.value == 0) {<br /> n.coins.now <- 1<br /> v.coins.now <- rep(0,n.dens)<br /> names(v.coins.now) <- denominations<br /> v.coins.now[as.character(i.denom)] <- 1 <br /> }<br /> ### if n.coins is better keep it<br /> if (n.coins.now < n.coins) {<br /> v.coins <- v.coins.now<br /> n.coins <- n.coins.now <br /> }<br /> } ## end loop for i.denomination<br /> exactCoin[i.value,] <- v.coins<br /> } ## end loop for i.value<br /> <br /> return(exactCoin)<br />}<br /><br /><br /><br />denominations <- c(25,10,5,1)<br />n.values <- 99<br />change.mat <- find.exact.change(n.values,denominations)<br />print(apply(change.mat,2,sum))<br /><br />denominations <- c(200,100,25,10,5,1)<br />n.values <- 499<br />change.mat <- find.exact.change(n.values,denominations)<br />print(apply(change.mat,2,sum))<br /><br />Anonymousnoreply@blogger.com