我们知道背包问题可以通过动态编程以O(nW)复杂度来解决.但我们说这是一个NP完全问题.我觉得这里很难理解.
(n是项目数.W是最大音量.)
我知道这Knapsack是NP完全的,而DP可以解决.他们说DP解决方案是pseudo-polynomial,因为它在"输入长度"(即编码输入所需的位数)中是指数的.不幸的是我没有得到它.有人能pseudo-polynomial慢慢向我解释那件事吗？
language-agnostic complexity-theory knapsack-problem dynamic-programming
algorithm ×1