4-21Discussion.ipynb

Kernel: Python 3 (system-wide)

Suppose that a company sells computer chips in packages of size 1, 5, and 8. Find the least number of packages that can be used to order 20 chips.

def chips(n):
    L = [0 for i in range(n)]
    L[0] = 1
    L[1] = 2
    L[2] = 2
    L[3] = 2
    L[4] = 1
    L[5] = 3
    L[6] = 3
    L[7] = 1
    for i in range(8, n):
        L[i] = 1 + min(L[i - 1], L[i - 5], L[i - 8])
    return L[n-1]

chips(20)

4