0
$\begingroup$

Given a set S = { $x_{1}$, $x_{2}$, . . . , $x_{n}$} where $x_{i} \in Z$ . and a K and it is $Z^{+}$ . The goal is to find k intervals $I_{1}, I_{2}, . . . , I_{k}$ so that each $x_{i}$ is in one of the intervals $I_{j}$ and so that the sum of the squared lengths of the intervals $I_{k}$ is as small as possible. For instance, S = {1, 3, 6} and K = 2, the best outcome is $I_{1}$ = [1, 3], $I_{2}$ = [6, 6], and the sum of squares of the lengths is 4.

We can approach our algorithm as: First of all, we sort S and let S = { $x_{1}$, $x_{2}$, . . . , $x_{n}$} where $x_{1}$<$x_{2}$<, . . . , <$x_{n}$. Then we can use dynamic programming. We let L[i, m] be the shortest sum of squared lengths of m intervals that cover all of $x_{1}$, . . . , $x_{i}$. Notice that L[1, m] = 0 for all 1 ≤ m ≤ k and L[i, 1] = ($x_{i}$$x_{1})^2$ for 1 ≤ i ≤ n. If we have a cover of $x_{1}$, . . . , $x_{i}$, suppose the interval that covers $x_{i}$ also covers all points $x_{j}$ , $x_{j+1}$, . . . , $x_{i}$. Then, the sum of the squared lengths is at least ($x_{i}$$x_{j}$ $)^2$ + L[i − 1, m − 1]. Therefore, the minimum such value is actually obtainable.

How can we know for sure "that L[1, m] = 0 for all 1 ≤ m ≤ k and L[i, 1] = $(x_{i} − x_{1})^2$ for 1 ≤ i ≤ n" and ?

Seem like we need to have a 2D-array? How can I visualize this solution better?

Here is what draw: enter image description here

How can we fill the 2D array with ($x_{i}$$x_{j}$ $)^2$ + L[i − 1, m − 1] ?

$\endgroup$
  • 2
    $\begingroup$ Please credit the original source of this exercise and of all copied text/material. Thank you! $\endgroup$ – D.W. Jan 30 at 18:55
  • 2
    $\begingroup$ We'd prefer that you ask only one question per post. I see three different questions here. $\endgroup$ – D.W. Jan 30 at 18:56

Your Answer

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

Browse other questions tagged or ask your own question.