The function $buttons$ has $8$ base cases which are the minimum number of packets to purchase for $n$ buttons where $0\leqslant{n}\leqslant{7}$.

$L(0) = 0$

$L(1) = 1$

$L(2) = 2$

$L(3) = 3$

$L(4) = 1$

$L(5) = 2$

$L(6) = 3$

$L(7) = 1$

For a number of buttons $n>7$, the vector $L$ is appended with the minimum value of the base cases $L$ after having subtracted the packet sizes $1,\ 4,\&\ 7$ from $n$, incrementing the total number of packets $i$ by $1$ in each iteration with the condition that $i\leqslant{n}$.

It then returns the final value of the vector $L$.

1

In [55]:

def buttons(n): L = [0, 1, 2, 3, 1, 2, 3, 1] if n > 7: i = 8 while i <= n: L.append(min(L[i-7],L[i-4],L[i-1])+1) i += 1 return L[-1] print('Minimum Packets: ', buttons(20))

2

Minimum Packets: 5

Alternatively, a greedy algorithm does actually works for $n=20$ buttons although it will not work for all values of $n$. The function $greedyButtons$ calculates the minimum number of packets required to purchase for $n$ buttons with $3$ base cases:

$n>=7$

$n>=4$

$n>=1$

The function returns a vector with the required number of each sized packet. The sum of this vector is the total minimum number of packets required to purchase to have $20$ buttons.

3

In [54]:

def greedyButtons(n): B=[0, 0, 0] while n>=7: n=n-7 B[0]+=1 while n>=4: n=n-4 B[1]+=1 while n>=1: n=n-1 B[2]+=1 return B P=greedyButtons(20) print('Packets of 7: ', P[0], '\nPackets of 4: ', P[1], '\nPackets of 1: ', P[2], '\nMinimum Packets: ', sum(P))

4

Packets of 7: 2
Packets of 4: 1
Packets of 1: 2
Minimum Packets: 5