Problem plecakowy?

Nie wiem jak algorytm tak naprawdę będzie do tego najlepszy.

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

Problem plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j–ty przedmiot jest wart c[j] oraz waży w[j]. Złodziej dąży do zabrania ze sobą jak najwartościowszego łupu, przy czym nie może zabrać więcej niż B kilogramów. Nie może też zabierać ułamkowej części przedmiotów (byłoby to możliwe w ciągłym problemie plecakowym).

Ale mam problem taki, że:
Plecaków może być kilka ustalam ile, oraz będą kwoty ujemne i musi tak pakować do plecaków, żeby nie zostały kwoty ujemne oraz wartość plecaka była dodatnia (Rozmiar plecaków taki sam)

Ale co to znaczy najlepszy?
Są 2 sprzeczne kryteria: jakość podawanych wyników oraz szybkość obliczeń.
Algorytmy dokładne będą powolne a heurystyki podadzą wynik szybko, ale może nie być optymalny.

Dla problemu ciągłego rozwiązaniem może być algorytm SIMPLEX, dla dyskretnego poszukaj w googlach coś na temat optymalizacji liniowej dyskretnej

Krolik napisał(a)

Ale co to znaczy najlepszy?
Są 2 sprzeczne kryteria: jakość podawanych wyników oraz szybkość obliczeń.

Jak to z większością algorytmów bywa, „najlepszy” to taki, który może nie daje zawsze optymalnego wyniku, ale bliski optymalnemu, oraz wykonuje się w rozsądnym czasie.

Spróbuj rozwiązać to genetycznie :)

Zanim spróbujesz genetycznymi, lepiej spróbuj VNS - dużo prostsze, mniej parametrów i działa na ogół znacznie lepiej (nie ma problemów z przedwczesną zbieżnością, ma mniejsze zapotrzebowanie na RAM, nakłada mniejsze wymagania na reprezentację rozwiązań - w sumie same zalety; nie bardzo widzę, w czym genetyczne mogą być lepsze). W sumie VNSa dla problemu plecakowego można zakodować w mniej niż 20 linijkach.

Co to znaczy

...będą kwoty ujemne i musi tak pakować do plecaków, żeby nie zostały kwoty ujemne...
?
Czy to znaczy, że do plecaka trzeba wziąć wszystkie elementy o ujemnych wartościach? Tak to trzeba rozumieć?</quote>