Como determinar o máximo número de itens de menor valor numa soma inteira composta por dois tipos de itens com valores fixos?

Minimizando o número de itens de maior valor e resolvendo a equação diofantina por teste de inteiros ou congruências modulares.

Para explicar: dados valores \(a\) (menor) e \(b\) (maior) e total \(S\), buscamos inteiros não negativos \(t,c\) tais que \(a t + b c = S\). Para maximizar \(t\) minimizamos \(c\): testar \(c=0,1,2,\dots\) ou resolver a congruência \(b c \equiv S \pmod{a}\) para achar o menor \(c\) válido; então \(t=(S-bc)/a\).

Exemplo:
Itens valem 12 e 30 pontos; total \(S=78\).
Resolver \(12t+30c=78\).
Em módulo 12: \(30c\equiv78\pmod{12}\) → \(6c\equiv6\pmod{12}\) → \(c\equiv1\pmod{2}\).
O menor \(c\ge0\) é \(c=1\), então \(t=(78-30)/12=4\).
Logo, o máximo de itens de 12 pontos é 4.