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}$$ A The 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.