Dyskretny problem plecakowy

Awatar użytkownika
qba
Użytkownik
Użytkownik
Posty: 138
Rejestracja: 23 sty 2006, o 21:51
Płeć: Mężczyzna
Lokalizacja: z zaskoczenia
Podziękował: 7 razy

Dyskretny problem plecakowy

Post autor: qba »

Witam,

Bardzo prosiłbym o wytłumaczenie czym różni się technika programowania dynamicznego od techniki z nawrotami, np. na przykładzie dyskretnego problemu plecakowego.
Awatar użytkownika
DEXiu
Użytkownik
Użytkownik
Posty: 1174
Rejestracja: 17 lut 2005, o 17:22
Płeć: Mężczyzna
Lokalizacja: Jaworzno
Pomógł: 69 razy

Dyskretny problem plecakowy

Post autor: DEXiu »

Hm. Nie wiem jakiego dokładnie tłumaczenia oczekujesz. Najprościej rzecz ujmując to programowanie z nawrotami to takie.. szukanie rozwiązań poprzez sprawdzanie "na pałę" wszystkich możliwości i w razie zabrnięcia sprawdzania w "ślepy zaułek" (tzn. braku rozwiązania dla już ustalonych warunków lub rozwiązania będącego nieoptymalnym) cofnięcia się i zmiany którejś z wcześniej wybranych opcji. W przypadku problemu plecakowego polegałoby to na "wrzucaniu do plecaka" po kolei każdego przedmiotu aż nie będzie można wrzucać więcej, pamiętaniu maksymalnej uzyskanej do tej pory wartości (i ewentualnie przedmiotów które dawały to rozwiązanie) i sprawdzeniu czy istnieje lepsze rozwiązanie poprzez "wyjęcie" ostatnio wrzuconych przedmiotów i próbę wrzucenia innych.
Natomiast programowanie dynamiczne prowadzi od razu do rozwiązania optymalnego poprzez konstruowanie go "od podstaw" na podstawie zapamiętywania optymalnych rozwiązań pomniejszych problemów i konstruowaniu z nich optymalnych rozwiązań problemów większych. W przypadku problemu plecakowego dyskretnego to będzie uzupełnianie tabelki której kolumny będą odpowiadały różnym pojemnościom plecaka, a wiersze wkładaniu kolejnych przedmiotów - zaczynamy od pierwszego przedmiotu wkładanego do plecaka o najmniejszej pojemności i uzupełniając kolejne komórki tabelki (na podstawie uprzednio uzupełnionych) szukamy wartości komórki odpowiadającej wszystkim przedmiotom w plecaku o zadanej pojemności.
Awatar użytkownika
qba
Użytkownik
Użytkownik
Posty: 138
Rejestracja: 23 sty 2006, o 21:51
Płeć: Mężczyzna
Lokalizacja: z zaskoczenia
Podziękował: 7 razy

Dyskretny problem plecakowy

Post autor: qba »

głównie tej tabelki w programowaniu dynamicznym nie jestem pewien,
wiem że wynik jest w ostatniej komórce np P[m,n] jednak nie wiem jak się go składa,
tzn nie wiem jak uzupełniać tabelkę po wpisaniu tych początkowych zer?
ODPOWIEDZ