CoCalc -- 11.15.ipynb

⁶¹ views
ubuntu2004

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 15 chips.

This problem looks similar to lightbulb problem we did in class. So we use the same algorithm here.

L[i] = least number of packages needed to put together an order of size i
if n > 8, L[n] = min(L[n-1],L[n-5],L[n-8]) + 1
L[0]=0,L[1]=1,L[2]=2,L[3]=3,L[4]=4,L[5]=1,L[6]=2,L[7]=3,L[8]=1

In [1]:

def chip(n):
    L = [0,1,2,3,4,1,2,3,1]
    if n > 8:
        i = 9
        while i <= n:
            L.append(min(L[i-1],L[i-5],L[i-8])+1)
            i += 1
    print(L)
    return L[n]

In [3]:

chip(15)

Out[3]:

[0, 1, 2, 3, 4, 1, 2, 3, 1, 2, 2, 3, 4, 2, 3, 3]

3

Product

Resources

Company