I have a proof, but it is hardly elegant. But it turns into a fairly simple procedure, which is easily extended to product II.
\(\displaystyle n \text { is a positive integer.}\)
\(\displaystyle \text {DEFINE: } k = \left \lfloor \dfrac{n}{5} \right \rfloor \text { and } m = n - 5k.\)
\(\displaystyle \therefore k \text { and } m \text { are integers, } n = 5k + m \text {, and } m = 1,\ 2,\ 3,\ \text { or } 4.\)
\(\displaystyle \text {DEFINE integers } x \text { and } y \text { such that (i) } 5x + 3y = n \text {, (ii) } x \ge 0 \le y \text {, and}\)
\(\displaystyle \text {(iii) if integers } a \text { and } b\ \exists \text { such that}\)
\(\displaystyle \text{(1) } 5a + 3b = n \text { and ( 2) } 0 \le b \ne y \text {, then } a + b > x + y.\)
Note that x and y may not exist for every value of n.
We need three lemmas. LEMMA 1 states that if y exists, then y = 0, 1, 2, 3, or 4. Proof follows.
\(\displaystyle \text {ASSUME non-negative integers } x \text { and } y \ \exists \implies 5x + 3y = n.\)
\(\displaystyle \text {ASSUME } y \ge 5.\)
\(\displaystyle \text {Let } a = x + 3 \text { and } b = y - 5 \implies a \text { and } b \text { are integers such that }\)
\(\displaystyle 5a + 3b = 5x - 15 + 3y + 15 = 5x + 3y = n \text { and } 0 \le b \ne 5.\)
\(\displaystyle \text {By definition then, } a + b > x + y.\)
\(\displaystyle \text {BUT } a + b = (x + 3) + (y - 5) = (x + y) - 2 < x + y \text {, a CONTRADICTION.}\)
\(\displaystyle \therefore y \not \ge 5 \implies y = 0,\ 1,\ 2,\ 3, \text { or } 4\ \because \text { by definition } y \text { is an integer } \ge 0.\)
LEMMA 2 states that if x exists, it does not exceed k. Proof follows.
\(\displaystyle \text {ASSUME non-negative integers } x \text { and } y \ \exists \implies 5x + 3y = n.\)
\(\displaystyle \text {ASSUME } x \ge k + 1 \implies 5x + 3y \ge 5(k + 1) + 3y \implies n \ge 5k + 5 + 3y \implies\)
\(\displaystyle 5k + m \ge 5k + 5 + 3y \implies 0 > m - 5 \ge 3y \implies y \not \ge 0\ \because \ m \le 4.\)
\(\displaystyle \text { BUT, by definition } y \ge 0 \text {, a CONTRADICTION.}\)
\(\displaystyle \therefore x \not \ge k + 1 \implies x < k + 1 \implies x \le k\ \because \text { by definition } x \text { is an integer.}\)
LEMMA 3 states that if x exists, it is k - 2, k - 1, or k. Proof follows.
\(\displaystyle \text {ASSUME non-negative integers } x \text { and } y \ \exists \implies 5x + 3y = n.\)
\(\displaystyle \text {ASSUME } x \le k - 3 \implies 5x + 3y \le 5(k - 3) + 3y \implies n \le 5k - 15 + 3y \implies\)
\(\displaystyle 5k + m \le 5k - 15 + 3y \implies 15 \le m + 15 \le 3y \implies 5 \le y\ \because \ 0 \le m.\)
\(\displaystyle \text {BUT, by LEMMA 1, } y \le 4 \text {, a CONTRADICTION.}\)
\(\displaystyle \therefore x \not \le k - 3 \implies x > k - 3 \implies x \ge k - 2\ \because \text { by definition } x \text { is an integer.}\)
\(\displaystyle \text {By LEMMA 2, } x \le k \implies x = k - 2,\ k - 1, \text { or } k \ \because \text { by definition } x \text { is an integer.}\)
Putting our lemmas together, there are exactly fifteen potential possibilities, and, by brute force, we can find x and y (if they exist) by examining all fifteen of them.
\(\displaystyle \text {I: } x = k - 2 \text { and } y = 0 \implies n = 5x + 3y = 5k - 10 \implies m = -\ 10 \text { FALSE.}\)
\(\displaystyle \text {II: } x = k - 2 \text { and } y = 1 \implies n = 5x + 3y = 5k - 10 + 3 \implies m = -\ 7 \text { FALSE.}\)
\(\displaystyle \text {III: } x = k - 2 \text { and } y = 2 \implies n = 5x + 3y = 5k - 10 + 6 \implies m = -\ 4 \text { FALSE.}\)
\(\displaystyle \text {IV: } x = k - 2 \text { and } y = 3 \implies n = 5x + 3y = 5k - 10 + 9 \implies m = -\ 1 \text { FALSE.}\)
\(\displaystyle \text {V: } x = k - 2 \text { and } y = 4 \implies n = 5x + 3y = 5k - 10 + 12 \implies m = 2 \text { OK.}\)
\(\displaystyle \text {VI: } x = k - 1 \text { and } y = 0 \implies n = 5x + 3y = 5k - 5 \implies m = -\ 5 \text { FALSE.}\)
\(\displaystyle \text {VII: } x = k - 1 \text { and } y = 1 \implies n = 5x + 3y = 5k - 5 + 3 \implies m = -\ 2 \text { FALSE.}\)
\(\displaystyle \text {VIII: } x = k - 1 \text { and } y = 2 \implies n = 5x + 3y = 5k - 5 + 6 \implies m = 1 \text { OK.}\)
\(\displaystyle \text {IX: } x = k - 1 \text { and } y = 3 \implies n = 5x + 3y = 5k - 5 + 9 \implies m = 4 \text { OK.}\)
\(\displaystyle \text {X: } x = k - 1 \text { and } y = 4 \implies n = 5x + 3y = 5k - 5 + 12 \implies m = 7 \text { FALSE.}\)
\(\displaystyle \text {XI: } x = k \text { and } y = 0 \implies n = 5x + 3y = 5k \implies m = 0 \text { OK.}\)
\(\displaystyle \text {XII: } x = k \text { and } y = 1 \implies n = 5x + 3y = 5k + 3 \implies m = 3 \text { OK.}\)
\(\displaystyle \text {XIII: } x = k \text { and } y = 2 \implies n = 5x + 3y = 5k + 6 \implies m = 6 \text { FALSE.}\)
\(\displaystyle \text {XIV: } x = k \text { and } y = 3 \implies n = 5x + 3y = 5k + 9 \implies m = 9 \text { FALSE.}\)
\(\displaystyle \text {XV: } x = k \text { and } y = 4 \implies n = 5x + 3y = 5k + 12 \implies m = 12 \text { FALSE.}\)
Thus, of the fifteen potential possibilities, only five are actual possibilities, namely V, VIII, IX, XI, and XII. Furthermore, each matches to a different possible value of m, and therefore we can reverse them. We can also see that if k = 0, only XI and XII result in a non-negative x so that V, VIII, and IX are impossible if n < 5. (That accounts for the lack of solutions if n = 1, 2, or 4.) Finally, if k = 1, V results in a negative x so that V is impossible if n < 10. (That accounts for the lack of a solutions if n = 7.)
So we have proved that there are solutions for x and y if n > 7 or if n = 3, 5, or 6. And the solutions can be found by the following algorithm, which is a fairly simple procedure.
\(\displaystyle m = 0 \implies x = k \text { and } y = 0.\) XI
\(\displaystyle m = 1 \implies x = k - 1 \text { and } y = 2.\) VIII
\(\displaystyle m = 2 \implies x = k - 2 \text { and } y = 4.\) V
\(\displaystyle m = 3 \implies x = k \text { and } y = 1.\) XII
\(\displaystyle m = 4 \implies x = k - 1 \text { and } y = 3.\) IX
EDIT: It occurs to me that you might be interested in minimizing the number of packages even if one package is not completely filled. Calculate k and m as above. If m = 0, use k packages of size 5. If m = 1, 2, or 3, use k packages of 5 and and 1 package of size 3. If m = 4, use k + 1 packages of size 5.