Informatyka MIMUW

Rozwiązanie każdego z poniższych zadań wymaga użycia jednej z trzech technik:
back-trackingu, programowania dynamicznego lub zachłannego.
Pytanie której?

1. [PCh, Zadanie o misjonarzach i kanibalach]
   Przez rzekę chcą przeprawić się kanibale i misjonarze.
   Kanibali i misjonarzy jest po trzech.
   Mają jedną łódkę, którą może płynąć do dwóch osób.
   Łódką umieją wiosłować kanibale i tylko jeden misjonarz.
   Jeżeli w dowolnej chwili, na dowolnym brzegu rzeki będzie więcej kanibali, niż misjonarzy, to zjedzą oni misjonarzy.

1. Jaka jest minimalna liczba monet lub banknotów potrzebna do wydania \(n\)zł reszty, przyjmując, że w obrocie są dostępne monety o zadanych (w postaci tablicy) nominałach?
2. Na ile sposobów można wydać \(n\) zł reszty przyjmując, że w obrocie są dostępne monety o zadanych (w postaci listy) nominałach.
3. Dana jest kwota \(k\) oraz zestaw nominałów banknotów \(b = [b_1; b_2; \dots; b_n]\).
   Mamy dowolną liczbę banknotów każdego z nominałów.