pablodmusumeci
BAN USERHere you have a Python implementation of the solution using DP. As a lot of people said, this is very similar to the Coin Change Problem
PACKAGES = [6,9,20]
def mc_nuggets(packages, n):
# partial_solutions[i] is True if exists a possible combination of packages for i
partial_solutions = [True]
for i in range(1, n + 1):
partial_solutions.append(any([partial_solutions[i - p] if (i - p) >= 0 else False for p in packages]))
#print "Partial:", list(enumerate(partial_solutions))
return partial_solutions[n]
assert mc_nuggets(PACKAGES,1) == False
assert mc_nuggets(PACKAGES,5) == False
assert mc_nuggets(PACKAGES,6) == True
assert mc_nuggets(PACKAGES,9) == True
assert mc_nuggets(PACKAGES,12) == True
assert mc_nuggets(PACKAGES,10) == False
assert mc_nuggets(PACKAGES,16) == False
assert mc_nuggets(PACKAGES,20) == True
assert mc_nuggets(PACKAGES,29) == True
assert mc_nuggets(PACKAGES,26) == True
assert mc_nuggets(PACKAGES,27) == True
To ensure that the new function has a uniform distribution we can do this:
- pablodmusumeci June 26, 20151) We are going to treat the 7 as a binary number 111
2) We are going to call rand5() for every single bit the seven has (3).
3) If the dice give us a {1,2} the bit is 0
If the dice give us a {3,4} the bit is 1
If the dice give us a 5 we call rand5() again.
4) If we end up with a 000 combination, we repeat the whole process because the result needs to be between 1 and 7.
This doesn't have a great performance, but I think this exercise cares more about the uniformity of the probability function than the execution time of it.