伪多项式时间复杂度

背包问题是典型的NPC问题，用动规求解的话，其复杂度为$O(mn)$，m为物品个数，n为背包大小。所以你可能奇怪，为什么这个复杂度看着明明是多项式时间，但为什么是NP问题？

这里就涉及到了伪多项式时间复杂度这个概念，请参考知乎回答。

一句话归纳：

​ 如果时间复杂度和输入数据的本身数值大小有关(传统公式里输入数据只代表规模，例如n个int整数)，那就是伪时间复杂度。