2
$\begingroup$

The problem is, we are given points $p_1,\ldots,p_n$ on positions of a length-$n$ binary sequence $x_1,\ldots, x_n$, and if the $i_{th}$ position of a sequence is $1$, then we "earn" $p_i$ points. So the total points is $\sum_{i=1}^{n}x_ip_i$. Our rule is that we cannot have three consecutive $1$'s, and we want to know what is highest possible points we can get from a length-$n$ sequence.

I propose an algorithm, but I find examples that leads to non-optimal solution. My algorithm basically goes as follows: let $P(k-1)$ be the highest possible points we can get for the length-$(k-1)$ sequence, with points $p_1,\ldots,p_{k-1}$, and it corresponds to an optimal length-$(k-1)$ sequence $s_{k-1}$, then I add an $1$ at $k_{th}$ position if it's possible to do so. If it is not possible to add $1$, then the previous 3 terms must be $011$. Then I compare $p_k,p_{k-1}$ and $p_{k-2}$, and put two $1$'s at two positions with the highest points, and put $0$ on remaining position. Hence I get $P(k)$, and $P(n)$ is computed by computing each $P(i)$.

However, consider the example of $n=4$, and $p_1=1,p_2=3,p_3=2,p_4=4$, this algorithm will produce $0101$, and $P(4)=7$, while $1101$ will have $8$ points.

Anyone has a suggestions on what is a true algorithm for this problem? Thanks!

$\endgroup$
2
$\begingroup$

Without loss of generality, assume $p_i> 0$. Otherwise we can set all $x_i=0$ where $p_i\le 0$ and consider the separated sequences by these $i$'s respectively.

Let $P(k)$ and $Q(k)$ be the highest possible points we can get for $p_1,\ldots,p_k$ where $x_{k-1}x_k=11$ and where $x_{k-1}x_k\neq 11$ respectively.

If the last two bits are $11$, $x_{k-2}$ must be $0$, and there are no constraint for $x_1,\ldots,x_{k-3}$, hence $$P(k)=p_{k-1}+p_k+\max\{P(k-3),Q(k-3)\}.$$

If the last two bits are not $11$, there are two cases: $01$ or $10$. Note to get the highest points, the last two bits cannot be $00$.

  • If the last two bits are $01$, there is no constraint for previous bits, the highest possible points are $p_k+\max\{P(k-2),Q(k-2)\}$.

  • If the last two bits are $10$, then $x_{k-3}x_{k-2}\neq 11$, the highest possible points are $p_{k-1}+Q(k-2)$.

So

$$Q(k)=\max\left\{p_k+\max\{P(k-2),Q(k-2)\},p_{k-1}+Q(k-2)\right\}.$$

Use the two recursion formulas above, you can compute the final result $\max\{P(n),Q(n)\}$.

$\endgroup$

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.