Internetowy solver problemu plecakowego

Rozwiązywanie problemu plecakowego 0/1

Problem plecakowy polega na wybraniu podzbioru przedmiotów o łącznej wadze nieprzekraczającej pojemności, tak aby zmaksymalizować sumę wartości. Ten solver stosuje klasyczne programowanie dynamiczne dla wariantu 0/1, co oznacza, że każdy przedmiot może być wybrany co najwyżej raz.

Przykład działania

Dla przedmiotów: A,2,6, B,3,10, C,4,12 i pojemności 5, maksymalna wartość wynosi 16, a wybrane przedmioty to A i B.

Parametry i ograniczenia

• Waga przedmiotu musi być dodatnią liczbą całkowitą nie większą niż pojemność.
• Wartość przedmiotu może wynosić od 0 do 1 000 000 000.
• Pojemność: liczba całkowita od 1 do 5000.
• Liczba przedmiotów: od 1 do 200.

Ograniczenia solvera

Narzędzie nie obsługuje wariantów ułamkowych, ograniczonej krotności, wielowymiarowych ani walutowych. Jeśli istnieje wiele optymalnych rozwiązań, zwracane jest tylko jedno, bez dodatkowych kryteriów (np. minimalnej wagi). Wartości należy traktować jako abstrakcyjne punkty, chyba że użytkownik sam dokona normalizacji jednostek.

Najczęstsze pytania

Jak sformatować dane wejściowe?

Każdy przedmiot w osobnej linii: nazwa,waga,wartość. Nazwa nie może być pusta i musi być unikalna. Waga i wartość to liczby całkowite.

Co oznacza „0/1” w nazwie?

Oznacza, że każdy przedmiot można wybrać tylko raz (nie można go dzielić ani powielać).

Czy mogę używać wag lub wartości dziesiętnych?

Nie, wagi i wartości muszą być liczbami całkowitymi. Wprowadzenie liczby dziesiętnej spowoduje błąd.