[ekr]

The knapsack Problem (the classic 0-1 version) is solvable through Dynamic Programming in O(n^2) time

The problem you described is the Multiple Knapsack Problem, which is indeed NP-complete.