Q: You are given an integer N and an integer M. You are supposed to write a method void findBestCoinsThatMinimizeAverage(int N, int M) that prints the best collection of N coins that minimize the average number of minimum coins needed to generate values from 1 to M. So, if M = 100, and N = 4, then if we use the set {1, 5, 10, 25} to generate each value from 1 to 100, so that for each value the number of coins are minimized, i.e. 1 = 1 (1 coin), 2 = 1 + 1 (2 coins),..., 6 = 1 + 5 (2 coins), ..., 24 = 10 + 10 + 1 + 1 + 1 + 1 (6 coins), and we take the average of these coins, we would see that the average comes out to ~5.7. But if we instead use {1, 5, 18, 25}, the average would come out to be 3.7. We are to find that set of N coins, and print them, that produce the minimum average.

I feel this is more of a math (dymanic programming) puzzle than an algorithm puzzle. I feel if we can figure out how to optimize for N=4,M=100, then we get a clue. In most currencies, there's a 50c coin, a 10c, 5c. Now, 1c is absolutely necessary to meet the first "trial" and out of the question. Let's start with 50/10/5/1 and see how to improve on it.

First, we need a simple function

map<int, int> findCombo (int target, set<int> coinSet);

For example, findCombo(24, set{1,5,10,25} ) == map{10-> 2, 1->4} Actually this findCombo is a tough comp science problem, but here we assume there's a simple solution.

Now, I will keep the same coinSet and call findCombo 100 times with target = 1,...100. We will then blindly aggregate all the maps. We need to minimize the total coins. (That total/100 would be the average we want to minimize.)

Now, the Impossibly Bad coinset would include just a single denomination of {1c}, violating the rule of N distinct denominations. Nevertheless, this coinset would give a total count of 1+2+3+...+100 = 5050. Let's assume the cost of manufacturing each big or small coin is identical, so that 5050 translates to the Impossibly Bad (IB) cost of $5050. Each legal coinset would give a saving off the IB cost level of $5050. We want to maximize that saving.

If we get to use a 25c once among the 100 trials, we save $24; if we get to use a 10c once, we save $9. If we use a poor coin set of {1c2c3c4c}, then the saving can only be $1, $2 or $3 each time.

## Thursday, June 14, 2012

### change-making problem

Labels: z_oq

## my favorite topics (labels)

_fuxi
(302)
_misLabel
(13)
_orig?
(3)
_rm
(2)
_vague
(2)
clarified
(58)
cpp
(39)
cpp_const
(22)
cpp_real
(76)
cpp/java/c#
(101)
cppBig4
(54)
cppSmartPtr
(35)
cppSTL
(33)
cppSTL_itr
(27)
cppSTL_real
(26)
cppTemplate
(28)
creditMkt
(14)
db
(65)
db_sybase
(43)
deepUnder
(31)
dotnet
(20)
ECN
(27)
econ/bank`
(36)
fin/sys_misc
(43)
finGreek
(34)
finReal
(45)
finRisk
(30)
finTechDesign
(46)
finTechMisc
(32)
finVol
(66)
FixedIncom
(28)
fMath
(7)
fMathOption
(33)
fMathStoch
(67)
forex
(39)
gr8IV_Q
(46)
GTD_skill
(15)
GUI_event
(30)
inMemDB
(42)
intuit_math
(41)
intuitFinance
(57)
javaMisc
(68)
javaServerSide
(13)
lambda/delegate
(22)
marketData
(28)
math
(10)
mathStat
(55)
memIssue
(8)
memMgmt
(66)
metaProgram`
(6)
OO_Design
(84)
original_content
(749)
polymorphic/vptr
(40)
productive
(21)
ptr/ref
(48)
py
(28)
reflect
(8)
script`/unix
(82)
socket/stream
(39)
subquery/join
(30)
subvert
(13)
swing/wpf
(9)
sysProgram`
(16)
thread
(164)
thread_CAS
(15)
thread_cpp
(28)
Thread*
(22)
timeSaver
(80)
transactional
(23)
tune
(24)
tuneDB
(40)
tuneLatency
(30)
z_ajax
(9)
z_algoDataStruct
(41)
z_arch
(26)
z_arch_job
(27)
z_automateTest
(17)
z_autoTrad`
(19)
z_bestPractice
(39)
z_bold
(83)
z_bondMath
(35)
z_book
(18)
z_boost
(19)
z_byRef^Val
(32)
z_c#GUI
(43)
z_c#misc
(80)
z_cast/convert
(28)
z_container
(67)
z_cStr/arr
(39)
z_Favorite*
(8)
z_FIX
(15)
z_forex
(48)
z_fwd_Deal
(18)
z_gz=job
(33)
z_gzBig20
(13)
z_gzMgr
(13)
z_gzPain
(20)
z_gzThreat
(19)
z_hib
(19)
z_IDE
(52)
z_ikm
(5)
z_IR_misc
(36)
z_IRS
(26)
z_javaWeb
(28)
z_jdbc
(10)
z_jobFinTech
(46)
z_jobHunt
(20)
z_jobRealXp
(10)
z_jobStrength
(15)
z_jobUS^asia
(27)
z_letter
(42)
z_linq
(10)
z_memberHid`
(11)
z_MOM
(54)
z_nestedClass
(5)
z_oq
(24)
z_PCP
(12)
z_pearl
(1)
z_php
(20)
z_prodSupport
(7)
z_py
(31)
z_quant
(14)
z_regex
(8)
z_rv
(38)
z_skillist
(48)
z_slic`Problem
(6)
z_SOA
(14)
z_spring
(25)
z_src_code
(8)
z_swingMisc
(50)
z_swingTable
(26)
z_unpublish
(2)
z_VBA/Excel
(8)
z_windoz
(17)
z_wpfCommand
(9)

## About Me

- familyman
- New York (Time Square), NY, United States
- http://www.linkedin.com/in/tanbin

## No comments:

Post a Comment