I found this code on the internet and i having hard time understanding it. Can anybody give some explanation it will be very helpful.
SubsetSum(n, W):
Initialize M[0,w] = 0 for each w = 0,...,W
Initialize M[i,0] = 0 for each i = 1,...,n
For i = 1,...,n: for every row
For w = 0,...,W: for every column
If w[i] > w: case where item can’t fit
M[i,w] = M[i-1,w]
M[i,w] = max( which is best?
M[i-1,w],
w[j] + M[i-1, W-w[j]]
)
Return M[n,W]
Classification
This is a typical application of Dynamic Programming.
Variables
Let w[i] denote the weight of item i, W the global capacity and M[i,w] the optimal solution of your subset sum problem using the first i objects and a remaining capacity w.
Key observation
To obtain the optimal solution M[i,w] from previous values M[i-1,*], we can either include the next item i or leave it out. If we include item i, then M[i,w] = w[i] + M[i-1, w-w[i]] (adding the weight w[i] for the inclusion of item i, but reducing the remaining capacity by the same amount; there is a typo on the slides involving j). If we leave item i out, then M[i,w] = M[i-1,w] (not adding any value to the previous solution and keeping the same remaining capacity).
We are interested in the optimal (maximal) solution, hence we take the maximum of those two values. In any case, we have reduced the index of M[i,*]. That means, if we know the values M[i',*], we can compute the values M[i,*] for i > i'. This is exactly the Dynamic Programming idea.
Note
The first lines are initialization and in the case where the value w[i] is greater than the remaining capacity w, we can obviously not include item i. The return value M[n,W] describes the optimal solution for including all items starting with the global capacity.