Annettuna on n kolikkoa ja summa x. Laske, mikä on suurin määrä kolikkoja, joilla summa voidaan muodostaa.
Voit olettaa, että 1 \le n \le 10 ja 1 \le x \le 100. Algoritmisi tulee toimia tehokkaasti kaikissa tapauksissa.
Toteuta tiedostoon maxcoin.py funktio find, joka palauttaa tehtävän vastauksen. Jos summaa ei ole mahdollista muodostaa mitenkään, funktion tulee palauttaa -1.
def find(x, coins):
# TODO
if __name__ == "__main__":
print(find(13, [1, 2, 5])) # 13
print(find(13, [2, 3, 5])) # 6
print(find(13, [2, 4, 6])) # -1
print(find(42, [8, 9, 11, 15])) # 5
Selitys: Kun x=13 ja kolikot ovat [2,3,5], optimiratkaisu on [2,2,2,2,2,3].