algorytm.org

Problem plecakowy



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Problem plecakowy
Ocena użytkowników:***** / 74
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 01 sierpnia 2005 22:11

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.

Poprawiony: 01 kwietnia 2008 11:28
Komentarze
photo
+1 # mateusz 2010-01-17 20:52
A...rozwiązanie jakiś?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # Daria 2010-02-19 10:48
Przydałby się jakiś mały przykładzik rozwiązania....
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-10 # gralichjunior 2010-05-14 11:07
ja to rozwiązałem i wynik wychodzi 14 (optymalne spakowanie naszego plecaka :-). Liczby jakie wprowadziłem to:
5 - par liczb
10 - pojemność plecaka

pary liczb:
5 3
3 4
2 2
4 6
3 1

i odpowiedź tak jak pisałem 14

nie wiem czy wypada wklejać rozwiązanie, może jak ktoś by chciał to najwyżej później wrzucę
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # rafal 2010-06-14 13:20
odp prawidłowa to liczby a2, a3,a4
waga wartosc
3-4
2-2
4-6

waga =9 czyli mniejsza niz 10, a wartość = 12 czyli czyli także zgodna z założeniami(y= \"a łączna wartość niemniejsza od 12\").
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz