An algorithm for solving the knapsack problem.

Suppose you are given positive integers K, x_1, x_2, ... x_n.  Here is an
algorithm which decides whether some subsequence of the {x_i} sums to K.

Let S[0..K] be an array of type boolean, indexed from 0 to K.

Initialize S as follows:
 S[0] = true, and S[i] = false for all 0 < i <= K.

For all i from 1 to n
 For all j from x_i to K
  S[j] = S[j] or S[j - x_i] // comment: if j < x_i, then S[j] is unchanged

If S[K] write YES else write NO.