Ogólny opis problemu plecakowego.
Dany jest plecak o pojemności b oraz zbiór A różnych przedmiotów {a1,a2...an}, z których każdy ma określony rozmiar s(ai) oraz wartość w(ai).
Problem plecakowy (decyzyjnie).
Parametry: skończony zbiór elementów A={a1,a2,...,an}, rozmiar s(ai) oraz wartość w(ai), będący liczbą naturalną, stała b=const. oznaczająca pojemność plecaka i y=const będąca wartością progową funkcji celu, w tym przypadku dolną granicą łącznej wartości pakowanych do plecaka przedmiotów.
Pytanie: czy istnieje podzbiór zbioru A, taki że:

• Suma rozmiarów elementów ai (s(ai)) jest niewiększa niż b (wszystkie przedmioty mieszczą się w plecaku)
• Suma wartości elementów ai (w(ai)) jest niemniejsza od y?

Przykład
Instancja : zbiór A składa się z 5 elementów o rozmiarach a1=5,a2=3,a3=2,a4=4,a5=3 i wartościach a1=3,a2=4,a3=2,a4=6,a5=1 oraz pojemność b=10 i stała y=12. Czy można dobrać tak elementy, by suma była niewiększa od pojemności plecaka a łączna wartość niemniejsza od 12?
Odpowiedź: tak.
Problem plecakowy (optymalizacyjnie).
Parametry: skończony zbiór elementów A={a1...a5}, z których każdy ma określoną rozmiar s(ai) i wartość w(ai), a także pojemność plecaka b=10.
Brak tu stałej y, ponieważ rozwiązanie wymaga ekstremalizacji funkcji celu. Należy znaleźdź taki podzbiór zbioru A,że łączny rozmiar elementów jest niewiększy od 10, a łączna wartość jest możliwie największa.

Komentarze