title: Balanced partition vs knapsack 1/0 complexity
body: <p>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.</p>
  
  <p>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 <a href="http://people.csail.mit.edu/bdean/6.046/dp/" rel="nofollow">here</a> that the knapsack problem is O(nC), while the balanced partition problem is O(n^2 k). What am I missing?</p>