就是作业四的某一题，他问说
一个复杂度为 O(nW) 的 0-1 knapsack 的算法是否为 polynomial time
我一开始的理解是，因为 W 和 n 并没有一定关系，所以不能确定它是否为polynomial
time
但在询问了某位上学期修过算法的强者之后，我大概了解题目想干嘛了～
就是在判断一个复杂度对 input 的大小为何种关系的时候，要有个比较的基准
比如说 merge sort ，复杂度 O(n lg n) ，比较的基准就是被排序的阵列大小 n
但是 n 和 W 之间没有特定的关系，没办法就 nW 来判断它是哪一种函数关系
因此要取它们共同的基准─ bit 的长度，来决定这个函数
首先 n 就是 item 数目的大小， n 个东西就 n 个 bit ( 1 或 0 代表拿或不拿)，所以
是线性的
至于 W ，是背包的大小，用 bit 来表示的话是一个二进制的数字
所以当 bit 长度变为 2 倍时， W 其实是变成 W^2 ，是指数关系
所以 nW 不是 polynomial time
如果有什么错的话还请不吝指教，谢谢！