We define a matrix T with n rows and b colons, where n is the number of items and b is the sum of the weights of all items. We say that the element at i row and j colon is true if there exists a subset of the first i items whose sum is equal to j.
The construction of this matrix is shown here.
In order to have the final answer we have to look at the last row of the matrix and we have to look for true element that minimises the maximum between j and b-j.
However, is this algorithm polynomial? Unfortunately, it is not polynomial. Actually, the complexity of this algorithm is called pseudo-polynomial. Because it is polynomial in of the value of the numbers, but it is exponential in the length of these numbers.
