4
Dlaczego problem plecakowy jest pseudowielomianem?
Wiem, że Knapsackjest to NP-kompletne, podczas gdy można to rozwiązać za pomocą DP. Mówią, że rozwiązanie DP jest pseudo-polynomial, ponieważ jest wykładnicze w „długości wejścia” (tj. Liczbie bitów wymaganych do zakodowania wejścia). Niestety nie dostałem. Czy ktoś może mi to wyjaśnić pseudo-polynomialpowoli?