# Dynamic Programming Subset Sum Problem with twist

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.

• So Here is where I am getting stuck at. Lets sort the weights in increasing order $\{w_1,......,w_i\}$. Now here is what I do know. If $|w_i - w_{i-1}| \ge \Delta$ then $|w_i - w_j| \ge \Delta$ for all $j < i$. So $$OPT(i,w) = \begin{cases} OPT(i-1, w) & : \text{if } w < w_i \\ OPT(i, w) = max(OPT(i-1, w), w_i + OPT(i-1, w-w_i)) & :\text{if } |w_i - w_{i-1}| \ge \Delta \end{cases}$$ – user2635911 Nov 5 '14 at 6:28
• But my problem arises when $|w_i - w_{i-1}| < \Delta$. Then I can have three scenarios. (1) The optimal solution has $w_i$. Which means that the optimal subset of $\{w_1,....,w_j\}$ where $j$ is closest weight to $i$ where $|w_i - w_j| \ge \Delta$ will also belong in optimal set. But the problem I'm having in the recursive formula is to how do I figure out that j? Is the only way to figure it out is to loop through all jobs backward from $i, i-1,....,j$? – user2635911 Nov 5 '14 at 6:28
• (2) Optimal solution contains $w_{i-1}$. Here all you do is call the recursive formula on the $i-1^{st}$ job. $OPT(i, w) = OPT(i-1,w)$ (3) Optimal solution contains neither $w_i$ or $w_{i-1}$. Here all you do to compute $OPT(i, w)$ is $OPT(i,w) = OPT(i-2, w)$. The biggest problem I'm having is with case (1). – user2635911 Nov 5 '14 at 6:33