Contact Us!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

| Download
Views: 25
Image: ubuntu2004
Tweet
Share
Share
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

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]

chip(15)
[0, 1, 2, 3, 4, 1, 2, 3, 1, 2, 2, 3, 4, 2, 3, 3]
3