Problem plecakowy - algorytm z nawrotami

Witam,

1.Problem plecakowy:
–Mamy zbiór przedmiotów, z których każdy ma wagę i wartość.
–Waga i wartość są wartościami całkowitymi, większymi od zera
–Złodziej planuje przenieść skradzione przedmioty w plecaku, ale plecak rozerwie się, jeżeli całkowita waga przedmiotów przekroczy pewną wartość W
–Zadaniem złodzieja jest znalezienie zbioru przedmiotów o największej wartości całkowitej bez przekroczenia maksymalnej wagi W

Możemy rozwiązać ten problem przy użyciu drzewa przestrzeni stanów:
–Poruszając się w lewo od korzenia dodajemy pierwszy przedmiot do plecaka, zaś w prawo odrzucamy go.
–Podobnie idziemy w lewo od węzła na poziomie 1, gdy dodajemy drugi przedmiot, a w prawo, gdy odrzucamy go, itd.
–Każda ścieżka od korzenia do liścia jest potencjalnym rozwiązaniem.

Problem jest problemem optymalizacyjnym.
–Oznacza to, że nie wiemy, czy węzeł zawiera rozwiązanie, dopóki nie zostanie zakończone przeszukiwanie.
–Jeżeli przedmioty dołączone aż do bieżącego węzła mają większą wartość niż najlepsze znalezione do tej pory rozwiązanie, zmieniamy wartość najlepszego dotychczas znalezionego rozwiązania.
–Jednak nadal możemy znaleźć lepsze rozwiązanie w jednym z węzłów podrzędnych („kradnąc więcej przedmiotów”)
–Z tego powodu w problemach optymalizacyjnych zawsze odwiedzamy węzły podrzędne obiecujących węzłów

2.Ogólny algorytm z powrotami dla problemów optymalizacyjnych

void checknode (node v)
{
  node u;
  if(value(v) is better than best) best = value(v);
  if(promising(v)) for(each child u of v) checknode(u);
}

Zmienna best ma wartość najlepszego znalezionego dotychczas rozwiązania, natomiast wartość value(v) stanowi wartość rozwiązania w węźle.
Po zainicjowaniu zmiennej best wartością mniejszą niż najgorsze potencjalne rozwiązanie na najwyższym poziomie przekazywany jest węzeł korzenia.

Węzeł jest obiecujący tylko wtedy, gdy możemy przejść do jego potomków.

3. Cechy pozwalające stwierdzić, że węzeł jest nieobiecujący

Cecha 1: osiągnięcie wagi niepozwalającej dodanie już żadnego przedmiotu
–Jeżeli weight jest sumą wag wszystkich przedmiotów dołączonych do określonego węzła, to węzeł jest nieobiecujący, gdy: weight >= W
(węzeł jest nieobiecujący nawet wtedy, gdy weight jest równe W, ponieważ w przypadku optymalizacji „obiecujący” oznacza, że powinniśmy przeglądać węzły potomne)

Cecha 2: (korzystamy z wniosków z algorytmu zachłannego)
–Wykorzystamy podejście zachłanne jedynie w celu ograniczenia zakresu przeszukiwania.
–Posortujmy przedmioty w porządku nierosnącym, według wartości pi/wi , gdzie wi oraz pi to odpowiednio waga i wartość i-tego przedmiotu.
–Założenie: Próbujemy określić czy bieżący węzeł jest obiecujący

–Niezależnie od tego, w jaki sposób próbowaliśmy wybrać pozostałe przedmioty, nie możemy uzyskać większego zysku, niż wówczas, jeżeli moglibyśmy skorzystać z ograniczeń ułamkowego problemu plecakowego od tego węzła dalej ( w problemie tym złodziej może ukraść dowolny ułamek z zabranych przedmiotów)
–Dlatego możemy znaleźć górną granicę zysku, jaki może zostać uzyskany poniżej bieżącego węzła.


====ALGORYTM====
–Niech profit będzie sumą zysków z przedmiotów dołączonych do bieżącego węzła
–Niech weight będzie sumą wag tych przedmiotów
–Inicjujemy zmienne bound (granica) oraz totweight wartościami profit oraz weight

–Następnie w sposób zachłanny zbieramy przedmioty, dodając ich wartości do zmiennej bound oraz ich wagi do zmiennej totweight, aż do natrafienia na przedmiot, który po zabraniu spowoduje przekroczenie przez totweight wartości W
–Następnie zabieramy ułamek przedmiotu, na jaki pozwala waga W i dodajemy wartość tego ułamka do ostatniej wagi.
–Jeżeli jesteśmy w stanie zabrać tylko ułamek wagi, węzeł ten nie może prowadzić do zysku równego bound, ale wartosć bound jest nadal górną granicą zysku, jaki możemy osiągnąć poprzez rozwinięcie tego węzła.

–Załóżmy, że węzeł znajduje się na poziomie i, a węzeł na poziomie k jest tym, który spowoduje przekroczenie przez sumę wag wartości W, wtedy:
                    totweight = weight + E ( suma od j=i+1 do k-1 ) wj
oraz
                    bound = ( profit + E ( suma od j=i+1 do k-1 ) pj ) + (W-totweight) * (pk/wk)
                         /zysk z pierwszych k-1 zebranych przedmiotow//pojemnosc k-tego przedmiotu//zysk na jednostke wagi/

–Jeżeli maxprofit ma wartość zysku najlepszego znalezionego do tej pory rozwiązania, to węzeł na poziomie i jest nieobiecujący, jeżeli:
bound <= maxprofit

Uwaga! Korzystamy tu z zasad algorytmu zachłannego jedynie w celu uzyskiwania granicy wskazującej nam, czy powinniśmy kontynuować rozwijanie węzła poniżej węzła bieżącego. Nie korzystamy z nich w celu zachłannego zbieranie przedmiotów bez możliwości późniejszej zmiany decyzji (jak jest to realizowane przez algorytm zachłanny)

JEŚLI KTOŚ TO WSZYSTKO PRZECZYTAŁ I ZROZUMIAŁ, TO WYRAZY UZNANIA ODE MNIE, SAM BYM ZAMKNĄŁ SZYBKO KARTĘ I POSZEDŁ ROBIĆ AMBITNIEJSZE RZECZY
Dane wejściowe:
4 16
40 2 20
30 5 6
50 10 5
10 5 2

n = 4, ilosc rzeczy ( ilosc wierszy ), W(wmax) = 16 ( pojemnosc plecaka, maksymalne upakowanie ), potem mamy n kolejnych wierszy w ktorych kolejno: cena przedmiotu, waga przedmiotu, cena na jednostke ( cena / waga )

Tłumaczę, jak ja to widzę: w mainie zmienna tablica -> przechowuje rekordy z danych wejsciowych, struktura o nazwie wezel, zawiera w sobie wszystkie potrzebne do operacji zmienne, w tym struktura ta posiada dwa wskazniki, wskazujace na ta strukture o nazwach: lewy i prawy, chodzi mi o to, ze w zaleznosci od danych warunkow bede przemieszczal sie do wezla ( wierzcholka konkretniej ) lewego lub prawego. Główny problem mam z wywoływaniem rekurencji w zależności właśnie od tego, czy ma iść do węzła lewego bądź prawego, niekiedy muszę się cofać o parę wierzchołków do góry, mam z tym problem. Zmienna poziom ustala mi poziom na jakim jest wykonywana dana operacja ( w prostym znaczeniu jest to indeks ).
Wyślę później jeszcze wyniki dla podanych danych wejściowych, kolejne operacje i zmienne jak się zmieniają, żeby zrozumieć problem.

dużo napisałeś, ale nie rozumiem Twojego problemu
z czym masz problem ?


"problem plecakowy" jest algorytmem z kanonu
jest omawiane w wielu miejscach np. na
http://algorytmy.info​/KodKontroler/kod/360/

I w czym masz problem? Bo z tematu wynika że już skończyłeś - na gotowe prace jest ten dział.

PS: Zostaw taki kod na kilka tygodni, wróć i spróbuj domyślić się co znaczą nazwy , , , , , , , , , , , , , ,  oraz co robią te gęsto zbite bloki pętli, zmiennych i ów - powodzenia.

O ile zrozumiałem to ma to być taki fikuśny generator kombinacji.Ale dlaczego jest on taki zawiły i nieczytelny?? I po co jako zmienna :cena na jednostke ( cena / waga ). To wynik dzielenia ). I po co wkładać ułamek przedmiotu??!!