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.

Poniższe zadania rozwiązuje się (mniej lub bardziej) zachłannie.
Dla każdego z nich, oprócz programu, należy uzasadnić poprawność rozwiązania zachłannego.

1. [CLR, p. 17.1]
   Problem wyboru zajęć (historyjka o kinomanie i jak największej liczbie filmów do obejrzenia).
2. Dany jest zbiór odcinków na prostej.
   Jaka jest minimalna liczba gwoździ, za pomocą których można je przybić do prostej?
   Każdy odcinek musi być przybity przynajmniej jednym gwoździem.
3. [CLR, ćw 17.2-4]
   Problem tankowania na stacjach benzynowych.