CoCalc Public FilesPackets of buttons.ipynb
Author: Julia Burnside
Views : 46
Compute Environment: Ubuntu 20.04 (Default)

Packets of Buttons

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$ but $1$ in each iteration with the condition that $i\leqslant{n}$.

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

In [53]:
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))

Minimum Packets: 5

The Greedy Method

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.

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))

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