Balanced partition vs knapsack 1/0 complexity

Question

Balanced partition: . You have a set of n integers each in the range 0 ... K. Partition these integers into two subsets such that you minimize |S1 - S2|, where S1 and S2 denote the sums of the elements in each of the two subsets. Knapsack problem: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. Cannot use the same object twice.

It seems that the solution to the Balanced partition problem is to simply apply the knapsack algorithm, for size of knapsack S/2, where S is the sum of all the input numbers, and the weight is equal to the value of each object. Still, it says here that the knapsack problem is O(nC), while the balanced partition problem is O(n^2 k). What am I missing?

Answer 1

Because C can be equal to k*n if every integer equals to k. So you get run-time of O(k * n^2) for the Integer knapsack problem in that case.