Problem plecakowy (knapsack problem) polega na wybraniu ze zbioru przedmiotów o określonej wartości i objętości takiego podzbioru, który zmieści się w plecaku o ograniczonej pojemności i maksymalizuje sumaryczną wartość przedmiotów. Istnieją dwa warianty problemu plecakowego: 0/1 (przedmiot można wybrać tylko raz lub nie wybrać wcale) i ciągły (można wybrać część przedmiotu). Jest to problem NP-trudny, co oznacza, że nie istnieje algorytm rozwiązujący ten problem w czasie wielomianowym dla dowolnego rozmiaru problemu.
Verified answer
Odpowiedź:
Problem plecakowy (knapsack problem) polega na wybraniu ze zbioru przedmiotów o określonej wartości i objętości takiego podzbioru, który zmieści się w plecaku o ograniczonej pojemności i maksymalizuje sumaryczną wartość przedmiotów. Istnieją dwa warianty problemu plecakowego: 0/1 (przedmiot można wybrać tylko raz lub nie wybrać wcale) i ciągły (można wybrać część przedmiotu). Jest to problem NP-trudny, co oznacza, że nie istnieje algorytm rozwiązujący ten problem w czasie wielomianowym dla dowolnego rozmiaru problemu.