主观题：The Knapsack Problem — 0-1 version

A knapsack with a capacity  $$M$$  is to be packed.  Given $$N$$ items.  Each item $$ i $$ has a weight  $$w_i$$  and a profit  $$p_i $$.  An **optimal packing** is a feasible one with maximum profit.  

This problem is NP-hard.

However, if no items have a size larger than $$N^2$$, is it still NP-hard?  Explain your answer.






答案：A DP solution is either $$O(N^2 P_{max})$$ or $$O(N W)$$.  If $$W$$ is a polynomial of $$N$$, then it can be solved in polynomial time.