Decyzyjny algorytm plecakowy dla dóch plecaków

Hej

Muszę zaimplementować algorytm plecakowy, tylko że problem tkwi w tym że nie jest to standardowy algorytm plecakowy, tylko decyzyjny (binarny) algorytm plecakowy dla dwóch plecaków (muszę wypełnić dwa plecaki o różnej pojemności pulą przedmiotów o jak największej wartości)

O ile już wiem jak zaimplementować algorytm dla jednego plecaka (używam metody programowania dynamicznego), o tyle zastanawiam się co z drugim plecakiem.
Pomysł był taki, żeby załadować jeden plecak, potem odrzucić przedmioty te które się znalazły w pierwszym i zrobić to dla drugiego, ale pierwsze wstępne próby na kartce pokazały że może to być nie optymalne ( a zależy mi na jak najbardziej optymalnym rozwiązaniu)

Czy macie może jakiś pomysł lub wskazówkę ?

Potraktuj plecaki tak, jak elementy, które mają być w nich umieszczone i zastosuj poznany algorytm do wypełnienia wszystkich plecaków. Na podstawie tego możesz określić właściwą kolejność wypełniania plecaków. Myślę, że program będzie wystarczająco szybki, ale tym przejmuj się dopiero po jego napisaniu.

A istnieje coś takiego jak optymalny algorytm pakowania plecaka?

http://pl.wikipedia.org/wiki​/Problem_plecakowy

http://pl.wikipedia.org/wiki​/Algorytm_pseudowielomianowy

Problem plecakowy jest NP-trudny i nie jest dla niego znany algorytm wielomianowy (gdyby istniał oznaczałoby to, ze P=NP). Znany jest jednak algorytm pseudowielomianowy dla tego problemu oparty na programowaniu dynamicznym.

http://en.wikipedia.org/wiki​/Knapsack_problem

_{» Dokumentacja ♦} problem NP-Trudny

/edit:

Problem plecakowy jest NP-trudny i nie jest dla niego znany algorytm wielomianowy (gdyby istniał oznaczałoby to, ze P=NP).

Podkreślony fragment tekstu jest jednak nieprawdziwy, bowiem w przypadku ewentualnego znalezienia algorytmu wielomianowego dla problemu plecakowego, problem plecakowy zostałby zaklasyfikowany do innej puli, a problemy NP byłyby nadal nietknięte.

@jankowalski25

Trochę nie mogę sobie wyobrazić w jaki sposób  traktować plecaki jak elementy, które mają być w nich umieszczone. Mam umieścić plecak w plecaku czy co ?

Najpierw używasz algorytmu, żeby znaleźć rozwiązanie, a później przetwarzasz wynik. Jeśli otrzymasz plecak w plecaku, to umieszczasz w danym plecaku elementy z tego plecaka, a nie sam plecak.

//edit: Upraszczając: Traktuj elementy jak pliki, a plecaki jak foldery.

//edit2: Przekładanie elementów z plecaka do plecaka wykonuj w trakcie obliczeń, bo inaczej możesz uzyskać nieprawidłowy wynik. Możesz również na początku ustalić właściwą kolejność (na wszelki wypadek wykonaj testy i sprawdź, czy wynik jest w porządku, bo nie jestem w 100% pewny tego algorytmu).