Dyskretny plecakowy- algorytmy z powrotami

Witam, mam zadanie z którym nie mogę sobie poradzić.
Rozwiąż dyskretny problem plecakowy, korzystając z metody algorytmy z powrotami.
Znalazłem taki pseudokod (o ile w ogóle jest poprawny), prosiłbym o wyjaśnienie co tam się dzieje, czym jest m1, m2, po co jest zamiana (w[n],w[i])

w - tablica wag
c - tablica wartości
P - pojemność plecaka
n - krok
cw - aktualna waga
v - wartość w plecaku
BBP(w,c,P,n,cw,v)  //problem plecakowy korzystając z algorytmów z powrotami
1. 	if n<len(w) then
2. 		for i <- n to len(w)
3. 			if cw+w[i] <= P then
4. 				v+=c[i]
5. 				cw+=w[i]
6. 				swap(w[n],w[i])
7. 				swap(c[n],c[i])
8. 				m1=BBP(c,w,P,n+1,cw,v)
9. 				swap(w[n],w[i])
10. 				swap(c[n],c[i])
11. 				v-=c[i]
12. 				cw-=w[i]
13. 			else
14. 				m2=bbp(c,w,P,n+1,cw,v)
15. 		return max(m1,m2)
16. 	else
17. 		return v 

Pozdrawiam

kiedy u mnie w pracy trzeba było zabrać się za algo do pakowania -> 2 tygodnie na czytanie literatury, jest mnóstwo podejść, najlepsze są te opublikowane i przetłumaczone przez uniwersytety azjatyckie, problem jest NP-Hard a metoda bruteforce już dla 6 paczek przekracza czas liczenia jednej sekundy.

zostaje Ci jedynie czytać literaturę z tym związaną i różne podejścia heurystyczne, no chyba, że bruteforce wystarczy to rekurencja i jedziesz każdy z każdym

Mogę prosić o jakieś naprowadzenie na źródła wiedzy ?

gosc24 napisał(a):

Mogę prosić o jakieś naprowadzenie na źródła wiedzy ?

W książce pt. "Algorytmy bez tajemnic" Thomas'a H. Cormen'a jest opisany ten problem. Tak, jak już wspomniał przedmówca, ten problem jest NP-trudny i nie można go rozwiązać algorytmem o złożoności wielomianowej. Oznacza to, że nie ma optymalnego rozwiązania tego problemu i żadnego problemu z tej klasy problemów.
Najprostsze rozwiązanie, to wypisanie wszystkich możliwych kombinacji. Wtedy masz złożoność obliczeniową: N! Dla 10! będzie ponad 3 miliony kombinacji i zwykły komputer sobie z tym pewnie poradzi, ale np. dla 20! i więcej wychodzą ogromne liczby i dla takich wartości nie ma sensu używać algorytmu Brute Force.
Nie znam metod heurystycznych umożliwiających rozwiązanie tego typu problemu. Możesz szukać w Google pod hasłami typu: heuristics, machine learning, artificial intelligence, etc. Ewentualnie, być może @gośćabc podzieli się z Tobą czymś bardziej konkretnym. ;-)