patternMinor
Minimizing the iterative sum of pairs of numbers in a list
Viewed 0 times
theminimizingiterativenumberssumlistpairs
Problem
Given the tuple (list, value):
$$\left(\left[x_1, x_2, \cdots x_n\right], y\right)$$
You may choose two adjacent values in the list to modify the tuple as:
$$\left(\left[x_1, x_2, \cdots x_{i-1}, (x_i + x_{i+1}), x_{i+2} \cdots x_n\right], y + x_{i} + x_{i+1}\right)$$
Iterate until:
$$\left(\left[\sum_i x_i\right], y + z\right)$$
What is the optimal set of choices that minimizes $z$?
Intuitively, you never want to operate on the largest number in the list. But the largest number in this list changes as you add values together. In other words, the optimal solution is not necessarily obtained by an optimal solution of a sub-problem.
A greedy solution would start by taking the smallest number in this list and adding it to the smaller of its adjacent numbers. This solution, while close, is not equivalent to the value returned by brute force search. This points to the fact the some locally optimal step is not globally optimal, which could be connected to the fact that the largest element of the list changes as values are added together.
$$\left(\left[x_1, x_2, \cdots x_n\right], y\right)$$
You may choose two adjacent values in the list to modify the tuple as:
$$\left(\left[x_1, x_2, \cdots x_{i-1}, (x_i + x_{i+1}), x_{i+2} \cdots x_n\right], y + x_{i} + x_{i+1}\right)$$
Iterate until:
$$\left(\left[\sum_i x_i\right], y + z\right)$$
What is the optimal set of choices that minimizes $z$?
Intuitively, you never want to operate on the largest number in the list. But the largest number in this list changes as you add values together. In other words, the optimal solution is not necessarily obtained by an optimal solution of a sub-problem.
A greedy solution would start by taking the smallest number in this list and adding it to the smaller of its adjacent numbers. This solution, while close, is not equivalent to the value returned by brute force search. This points to the fact the some locally optimal step is not globally optimal, which could be connected to the fact that the largest element of the list changes as values are added together.
Solution
I will assume that initially $y=0$, as this makes no difference in your problem.
Look at the very last two elements $a,b$ that you will apply your operation on:
The tuple is $([a,b], y$) and, at the next iteration, it will necessarily be $([a+b], $y+a+b$)$, since $a+b = \sum_{i=1}^n x_i$ is a constant, you only want to minimize $y$.
Notice that $a$ (resp. $b$) must have been obtained as a sum of some contiguous sequence of elements of your list starting from $x_1$ (resp. ending in $x_n$).
Calling $OPT[i,j]$ the minimum value of $y+z=z$ in your problem when the input instance consists of $([x_1, \dots, x_j], 0)$, we then obtain (for $n > 1$):
$$
OPT[1,n] = \sum_{h=1}^n x_h + min_{h=1,\dots,n-1} \left\{ OPT[1,h] + OPT[h+1,n] \right\}
$$
and, in general:
$$
OPT[i,j] =
\begin{cases}
\sum_{h=i}^j x_h + min_{h=i,\dots,j-1} \left\{ OPT[i,h] + OPT[h+1,j] \right\} & \mbox{if } j-i>0 \\
0 & \mbox{if } j-i = 0
\end{cases}.
$$
There are $O(n^2)$ subproblems and each requires taking a minimum over $O(n)$ elements, so your problem can be solved in $O(n^3)$ time via dynamic programming.
Look at the very last two elements $a,b$ that you will apply your operation on:
The tuple is $([a,b], y$) and, at the next iteration, it will necessarily be $([a+b], $y+a+b$)$, since $a+b = \sum_{i=1}^n x_i$ is a constant, you only want to minimize $y$.
Notice that $a$ (resp. $b$) must have been obtained as a sum of some contiguous sequence of elements of your list starting from $x_1$ (resp. ending in $x_n$).
Calling $OPT[i,j]$ the minimum value of $y+z=z$ in your problem when the input instance consists of $([x_1, \dots, x_j], 0)$, we then obtain (for $n > 1$):
$$
OPT[1,n] = \sum_{h=1}^n x_h + min_{h=1,\dots,n-1} \left\{ OPT[1,h] + OPT[h+1,n] \right\}
$$
and, in general:
$$
OPT[i,j] =
\begin{cases}
\sum_{h=i}^j x_h + min_{h=i,\dots,j-1} \left\{ OPT[i,h] + OPT[h+1,j] \right\} & \mbox{if } j-i>0 \\
0 & \mbox{if } j-i = 0
\end{cases}.
$$
There are $O(n^2)$ subproblems and each requires taking a minimum over $O(n)$ elements, so your problem can be solved in $O(n^3)$ time via dynamic programming.
Context
StackExchange Computer Science Q#115422, answer score: 2
Revisions (0)
No revisions yet.