Question:  You are given an input , which is a sequence of positive integers $w_1, w_2, . . . , w_n$ with parameters $W, . $We wish to find$S  \{1, 2, . . . , n\}$ such that $\sum_{j \in S} w_j$ is as large as possible, subject to the constraints that (a)$\sum_{j \in S} w_j W$,and (b) for all $i, j  S$, if $i \neq j$ then $|w_i  w_j |  .$Here is the recursive formula I came up with (which is incorrect).$$OPT(i,w) = \begin{cases} OPT(i-1, w) & : \text{if  } w < w_i  \\ w_1 & : \text{if   } i = 1 \text{and  } w_1 \le W\\OPT(i, w) = max(OPT(i-2, w), OPT(i-1, w), w_i + OPT(i-2, w-w_i)) & : \text{if  } |w_i - w_{i-1} | < \Delta\\OPT(i, w) = max(OPT(i-1, w), w_i + OPT(i-1, w-w_i)) & : otherwise\end{cases}$$AThe problem with the above formula is that it only checks if the $i-1^{st}$ weight is compatible with the $i^{th}$. It doesn't check if the $i^{th}$ weight is compatible with all the weights in the optimal solution. For example, if $\Delta = 2, W = 6, w_1 = 3, w_2 = 1, w_3 = 2$ then the recursive formula returns 5 instead of 3. I would appreciate any help. Thanks.
Dynamic Programming Subset Sum Problem with twist
dynamic programming