buy_coke - min_coin_cnt

min_coin_cnt.py

cache = dict()
def min_coin_cnt(i, j, k, n):
    """
    assert i + j*5 + k * 10 >= n * 8
    """
    if n == 0:
        return 0
    elif (i, j, k, n) in cache:
        # print("HIT  ", (i,j,k,n), '=', cache[(i,j,k,n)])
        return cache[(i,j,k,n)]
    cnt = 1000000 # big enough
    if i >= 8:
        st = min_coin_cnt(i - 8, j, k, n - 1) + 8
        cnt = min(cnt, st)
    if i >= 3 and j >= 1:
        st = min_coin_cnt(i - 3, j - 1, k, n - 1) + 4
        cnt = min(cnt, st)
    if j >= 2:
        st = min_coin_cnt(i + 2, j - 2, k, n - 1) + 2
        cnt = min(cnt, st)
    if k >= 1:
        st = min_coin_cnt(i + 2, j, k - 1, n - 1) + 1
        cnt = min(cnt, st)
    if i >= 3 and k >= 1:
        st = min_coin_cnt(i - 3, j + 1, k - 1, n - 1) + 4
        cnt = min(cnt, st)
    cache[(i,j,k,n)] = cnt
    # print("CACHE", (i,j,k,n), '=', cnt)
    return cnt

def run(n, i, j, k):
    assert i + j*5 + k * 10 >= n * 8
    cache.clear()
    print(min_coin_cnt(i, j, k, n))

notes.txt

strategy for single purchase behavior
--------------------------------------------
   coin     |     change    |   coin count
1   5   10  |   1   5   10  |
----------------------------|---------------
8           |               |       8
3   1       |               |       4
    2       |   2           |       2
        1   |       2       |       1
3       1   |       1       |       4
--------------------------------------------

assume we have i*1 + j*5 + k*10 left, and we need to buy n coke
f(i, j, k, n) = ?
=> min ...
f(i - 8, j, k, n - 1) + 8          , i >= 8
f(i - 3, j - 1, k, n - 1) + 4      , i >= 3 & j >= 1
f(i + 2, j - 2, k, n - 1) + 2      , j >= 2
f(i + 2, j, k - 1, n - 1) + 1      , k >= 1
f(i - 3, j + 1, k - 1, n - 1) + 4  , i >= 3 & k >= 1

remarks: use cache to optimize

test.py

%time run(2,2,1,1)

# 5
# CPU times: user 0 ns, sys: 0 ns, total: 0 ns
# Wall time: 87.7 µs




%time run(100, 300, 100, 20)

# 300
# CPU times: user 492 ms, sys: 0 ns, total: 492 ms
# Wall time: 489 ms