I am trying to understand the knapsack problem from the book: Algorithm Design
Equation (1) deals only with the case when nth item is too big. But why in the “Otherwise” case we have included the case when ith item is greater than the limit. I think i=n in the “Otherwise” part
Some body please guide me that the “Otherwise” part would be executed only when the ith item would be greater than the W so why we have included the condition of nth case (i.e. when i=n) in the otherwise part (we are already dealing this case in the "if condition", what is the purpose of max?
If $w_i$ is small enough to be used, then there are two cases to consider for an optimal solution - it either uses $w_i$ or it doesn't.
If the optimal solution does not use $w_i$, then it is just the same as the optimal solution you would get if $w_i$ were not available at all. The optimal solution in this case is $OPT(i-1,w)$, getting as close to $w$ using the other $i-1$ weights.
If the optimal solution does use $w_i$, then the removing $w_i$ from it gives us an optimal solution of the smaller problem of trying to reach a goal of $w-w_i$ using the rest of the weights. So if we remove $w_i$ from the optimal solution we get $OPT(i-1,w-w_i)$. Adding $w_i$ back again we get $w_i+OPT(i-1,w-w_i)$.
We don't really know whether the optimal solution uses $w_i$ or not, but in one case it gives the result $OPT(i-1,w)$, in the other it gives $w_i+OPT(i-1,w-w_i)$. The actual optimal solution is the largest of these two possibilities, i.e. the $max$ of them.