我知道这Knapsack是NP完全的,而DP可以解决.他们说DP解决方案是pseudo-polynomial,因为它在"输入长度"(即编码输入所需的位数)中是指数的.不幸的是我没有得到它.有人能pseudo-polynomial慢慢向我解释那件事吗？
Knapsack
pseudo-polynomial
language-agnostic complexity-theory knapsack-problem dynamic-programming
complexity-theory ×1
dynamic-programming ×1
knapsack-problem ×1
language-agnostic ×1