Alpinista i jego plecak
Alpinista pakuje plecak, przygotowując się do ekstremalnej wyprawy w Bitogóry. Musi zabrać ze sobą pewną ilość opakowań rozmaitych rodzajów żywności. Może on wybierać spośród zbioru N opakowań różnych produktów, z których każde ma określoną objętość Vi oraz wartość kaloryczną Ki na opakowanie (i = 1, 2, …, N). Jego plecak ma pojemność P i zapewne nie wszystkie produkty się w nim zmieszczą. Chciałby jednak zapakować produkty o łącznej maksymalnej wartości kalorycznej. Musisz dopomóc mu w tym, pisząc odpowiedni program w trzech wariantach:
- wyznaczający wszystkie podzbiory zbioru produktów i wybierający najlepszy z nich,
- wykorzystujący algorytm z powrotami,
- wykorzystujący metodę programowania dynamicznego.
Skoczek na szachownicy
Skoczek (koń) szachowy porusza się po szachownicy w charakterystyczny sposób: o dwa pola na wprost i jedno w bok pod kątem prostym. Jeśli skoczka ustawimy na szachownicy o wymiarach N×N, wtedy zachowując odpowiednią sekwencję ruchów jesteśmy w stanie obejść całą szachownicę odwiedzając każde pole dokładnie raz. (Nie dla wszystkich N jest to możliwe). Napisz program wykorzystujący algorytm z powrotami, który dla danego N symuluje taki spacer skoczka (na przykład wypisując sekwencję współrzędnych pól szachownicy) lub stwierdza, że nie da się tego zrobić.
Cykl Hamiltona
Dany jest spójny graf nieskierowany. Należy rozstrzygnąć, czy istnieje w nim cykl Hamiltona, czyli taka ścieżka, która wychodząc z pewnego wierzchołka grafu przechodzi przez wszystkie jego wierzchołki odwiedzając je tylko raz i dociera do wierzchołka startowego (tym samym odwiedzając go drugi raz). Graf posiada V wierzchołków oraz E krawędzi.
Oto przykład cyklu Hamiltona w grafie (krawędzie w kolorze czerwonym):
Połowa kwoty
Dwóch przyjaciół wypłaciło z banku pewną kwotę bitalarów. Poniewczasie okazało się, że mogą pojawić się problemy z podziałem tej kwoty na dwie równe części. Pieniądze wypłacono używając N różnych nominałów banknotów, przy czym banknotów o nominale Wi było Si sztuk (i = 1, 2, …, N). Napisz program wykorzystujący algorytm z powrotami, który odpowiada na pytanie, czy da się podzielić tę kwotę na połowy bez rozmieniania banknotów. A może znajdziesz inny sposób rozwiązania tego problemu?
Powrót do Algorytmy wykładnicze