Let $A=\{a_{1}...,a_{N}\}$ and $B=\{b_{1},...,b_{M}\}$ be finite sets of integers, such that $N \geq M$.
Find a mutually-exclusive covering of size $M$: $A_{1},...,A_{M}⊂A$ that is monotonic, meaning: if $a_{i} \in A_{l}$ and $a_{j} \in A_{m},$ and $l > m$, then necessarily $i\geq j$. And finally, I want the matching to minimize:
$$\sum_{k=1}^{M} \Bigg| b_{k} - \bigg(\sum_{a\in A_k} a\bigg)\Bigg|.$$
I'm not sure I've formulated this correctly, so here's the actual setup I'm interested in:
I have a paragraph of text in two languages ($A$ and $B$). Each is composed of sentences of differing lengths (e.g. the 1st sentence in $A$ is of length $a_{1}$, and $A$ has $N$ sentences, $B$ has $M$ sentences). I want to match the sentences: for instance, the 3rd and 4th sentences in $A$ are a translation of the 3rd sentence of $B$.
Here is an example for lengths of $A$ and $B$:
$A = [56, 156, 117, 170, 214, 97, 454, 177, 141, 173, 102, 90, 295, 259, 222, 54, 36, 152, 178, 154, 100, 117, 315, 375, 155, 72]$
$B = [59, 192, 114, 156, 221, 537, 149, 158, 176, 72, 92, 297, 320, 180, 68, 36, 133, 144, 179, 79, 163, 277, 487, 75]$
I hope it makes sense; Also an approximate solution would help.
Perhaps this better fits stackoverflow? thanks for any kind of help!
A sketch of the solution:
Denote by $t[n][m]$ the cost of the best matching of $a_1,\ldots,a_n$ to $A_1,\ldots,A_m$ and observe, that we can calculate $t[n][m]$ using only the values of $t[i][j]$ for smaller values of $i$ and $j$. More precisely, we define $t : \{0,\ldots,N\} \times \{1,\ldots,M\} \to \mathbb{N}$ as
$$ t[n][m] = \begin{cases} \displaystyle0 & \text{ if } n = 0, \\ \displaystyle\Big|b_1 - \sum_{k=1}^{n}a_k\Big| & \text{ if } m = 1, \\ \displaystyle\min_{i = 0}^{n} \left(t[i][m-1] + \Big|b_m - \sum_{k=i+1}^{n}a_k\Big|\right) & \text{ otherwise}. \\ \end{cases} $$
This algorithm will take $O(N^2M)$ time to calculate $t[N][M]$, which will be the cost of the solution you are looking for. To construct the actual matching just store the indices that realize the minima, and you will be able to reconstruct exactly the whole partition.
I hope this helps $\ddot\smile$