1
$\begingroup$

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.

Improve this question
$\endgroup$
2
$\begingroup$

Hint: Arrange the weights in increasing order. You might also need to make other changes, but sorting the weights is a good first step.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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}$$ $\endgroup$ – user2635911 Nov 5 '14 at 6:28
  • $\begingroup$ 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$? $\endgroup$ – user2635911 Nov 5 '14 at 6:28
  • $\begingroup$ (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). $\endgroup$ – user2635911 Nov 5 '14 at 6:33
  • $\begingroup$ In your dynamic programming table, you need to "remember" also the largest weight that you put in. This will solve your problems. $\endgroup$ – Yuval Filmus Nov 5 '14 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.