Algorytmy wykładnicze - Zadania

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:

  1. wyznaczający wszystkie podzbiory zbioru produktów i wybierający najlepszy z nich,
  2. wykorzystujący algorytm z powrotami,
  3. 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):

prob01.gif

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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License