Hadron DaVinci

Minimum and maximum number of coins needed to make change for a $100 dollar bill? (Unbounded)

12 Sep 2020 - Hadron DaVinci

Problem

You have unlimited $20 dollar bills, unlimited $10 dollar bills, unlimited $5 dollar bills, and unlimited $1 dollar bills.
How many ways can you make change for a $100 dollar bill?

Discussion

Truths:

1. This scenario is unbounded since the number of each bill available is unlimited.
2. Even though this problem uses bills as the form of currency, it is equivalent to coins. Therefore, this is still a coin problem.
   
   

Method (Coin Change Mother Function):

In a previous post, I created a function which could be used to solve many coin change problems.
Internally, it uses a double loop along with recursion to create a list of coins that sum to the target value.
You can find more about that post here.

Example

import sys

coin_values = [20, 10, 5 1]
quantity = [sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize]
target_value = 100
SOLUTIONS = []

foo(coin_values, quantity, target_solutions)
max_count = 0
min_count = 0

for s in SOLUTIONS:
    max_count = max(len(s), max_count)
    min_count = min(len(s), min_count)

print("Max Number of Bills Needed Is:", max_count)
print("Min Number of Bills Needed Is:", min_count)