Troco Mínimo
Você trabalha em uma loja e precisa dar troco ao cliente. Você possui moedas de $N$ denominações distintas e pode usar cada denominação ilimitadas vezes. Dado um valor de troco $V$, determine o menor número de moedas necessário para compor exatamente esse valor.
Input
A primeira linha contém dois inteiros $N$ e $V$ $(1 \le N \le 100,\ 1 \le V \le 10^6)$.
A segunda linha contém $N$ inteiros distintos $c_i$ $(1 \le c_i \le 10^4)$, os valores das moedas disponíveis. É garantido que sempre existe uma moeda com valor 1, portanto é sempre possível compor qualquer valor $V$.
Output
Imprima um único inteiro: o menor número de moedas para totalizar exatamente $V$.
4 11 1 4 6 10
2
Explanation 1:
Com moedas $\{1, 4, 6, 10\}$, a melhor combinação para $11$ é $10 + 1 = 11$, com apenas **2 moedas**.
3 8 1 4 6
2
Explanation 2:
A abordagem gulosa escolheria $6 + 1 + 1 = 8$ com **3 moedas**, mas o ótimo é $4 + 4 = 8$ com apenas **2 moedas**. Esse exemplo ilustra por que o algoritmo guloso não funciona para denominações arbitrárias.
4 15 1 5 10 25
2