Matching problem



The following matching problem has arisen in a project I'm working on.
Consider a target array of integers:

target = 5,2,6,3,2,4,6,8

And a number of smaller source arrays:

A = 2,3,1
B = 7,4
C = 1,2
D = 3,5
E = 6

Now, the source arrays should be concatenated to an array that as
closely as possible matches the target. The distance between two
individual elements is f(a,b) = (a-b)^2, and the distance of the
created array to the target is the sum of all individual distances. If
the created array is larger than the target, any subarray of it can be
used for the match. It is not necessary to use all of the source
arrays, but each source array may only be used once!

For example, the optimal solution to the above problem is to put the
arrays in the order A,E,C,D,B, this yields the array
2,3,1,6,1,2,3,5,7,4, and removing the first and last elements gives the
following match:

5 2 6 3 2 4 6 8 (target)
3 1 6 1 2 3 5 7 (created array)
-----------------------
4 1 0 4 0 1 1 1 (individual distances)

Total distance = 12

I am wondering if there is a (somewhat) efficient algorithm to solve
this problem for the following size:

Number of source arrays: 5000
Source array lengths: 5-20
Target length: 10000
Integer range: 8-bit (0-255)

My best idea so far is a kind of dynamic dijkstra, but it is too slow
for the size of the problem.

What makes me think there might be a solution is that I have been able
to solve two variations of the problem efficiently:

1. Source arrays are allowed to repeat, solved easily with dynamic
programming.

2. Source arrays are all of the same length, solved with weighted
bipartite matching.

Thanks for any help,

Mattias

.