I am trying to understand the knapsack problem from the book:
I can’t understand the following equation. This provides solution to knapsack problem in the context of Dynamic programming. So we have S small problems. But I can’t understand what is meant by max S summation of weight over subscript j.
Some body please guide me.
Zulfi.
It means the maximum value of the sum of weights of items in $S$, considering all possible choices of $S$ that satisfy the two specified restrictions. It can also be written as $$\max\left\{\sum_{j\in S} w_j: S\subseteq\{1,\dots,i\} \text{ and } \sum_{j\in S} w_j\le w\right\}.$$