In [ ]:

# 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.

1

In [23]:

def package(n): L = [0 for i in range(n)] L[0] = 1 # Given: size 1 chip = 1 package L[1] = 2 # solved: size 2 chips = 2 package (solve by hand) (1+1) L[2] = 3 # solved: size 3 chips = 3 package (solve by hand) (1+1+1) L[3] = 4 # solved: size 4 chips = 4 package (solve by hand) (1+1+1+1) L[4] = 1 # Given: size 5 chips = 1 package L[5] = 2 # solved: size 6 chips = 2 package (solve by hand) (5+1) L[6] = 3 # solved: size 7 chips = 3 package (solve by hand) (5+1+1) L[7] = 1 # Given: size 8 chips = 1 package for i in range(8,n): L[i] = 1 + min(L[i-1],L[i-5],L[i-8]) print(L) return L[n-1]

2

In [24]:

package(20)

3

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

4

In [ ]:

4