1
$\begingroup$

I was trying to solve this problem using dynamic programming.

We have $n$ objects in a row where each object has a value represented with a positive number. This is encoded with an array $V[1], . . . , V[n]$ where $V [1]$ is the value of the first object in the row, $V [2]$ is the value of the second object in the row and so on. We want to select a set $I \subseteq \{1, . . . , n\}$ of objects in such a way that the sum of its values, $\sum\limits_{i\in I} V [i]$, is as large as possible. However, we cannot select objects that occupy consecutive positions in the row. That is, if we select object $i$, then we cannot select object $i − 1$ nor object $i + 1$. For example, if $V = (6, 4, 3, 7, 3)$ then the best option would be to select the first object (with value $6$) and the fourth object (with value $7$). It is easy to see that any other option would have smaller total value. We want a dynamic programming algorithm that, given as input array $V$ , computes the value of the set with highest value. Note that, in order to simplify matters, we do not ask that the algorithm returns the set, only its total value.

The probleem comes when it says "we cannot select object $i − 1$ nor object $ i + 1$". For $i-1$, the recursive case should be Optimal$(j-2)$+Value$(j)$, but no idea about $i+1$.

$\endgroup$
1
$\begingroup$

For $k \in [\![1, n]\!]$, you can define $f(k)$ as the maximum value reachable using objects $1$, $2$, …, $k$, without two consecutives objects.

Now the key to the dynamic programming implementation is to see that:

$\forall k \in [\![3, n]\!], f(k) = \max(f(k-1), f(k-2) + V[k])$

The reason is that to compute $f(k)$, you can either keep the $k$-th object or not. If you keep it, then you cannot keep the $k-1$-th object.

Finally, you want to compute $f(n)$.

$\endgroup$
2
  • $\begingroup$ Then the case base, should be something like if k=1 we get V1, if k=2 we get max(V1, V2)?? $\endgroup$
    – hcr2077
    Apr 7 at 18:29
  • $\begingroup$ Yup, that is correct. $\endgroup$
    – Nathaniel
    Apr 7 at 18:58

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.