# Is there a way to find the fixed size subsequence sum in an N by M array that is the closest to a given N-dimensional vector?

Basically, I need to solve the multivariate case of the "closest subsequence sum to a given value K" problem, which is solved with dynamic programming as far as I understand. Let's say I have M rows of integer data.

A = [
[a11, a12, .., a1n],
...
[ai1, ai2, .., ain],
...
[am1, am2, .., amn]
]


And I have a target vector K: K = [k1, .., kn]

In other words, I need to approximately solve the following system of linear equations:

w1*a11 + .. + wm*am1 = k1
...
w1*a1n + .. + wm*amn = kn


Where w1..wn can only assume values on 0 and 1, so it feels like a case of diophantine equations of sorts. I can't quite come up with a solution yet.

Another constraint is to have the closest subsequence of a fixed size, i.e. w1+ ... + wm = S. For example, I have 10000 rows and I want to find the 300 rows the sum of which will give me something close to my target vector K.

In particular, replace the vector $$(a_{i1},\dots,a_{in})$$ with the vector $$(a_{i1},\dots,a_{in},c,0,0,\dots,K,0,\dots,0)$$, where the $$K$$ is in the $$i$$th position, $$K$$ is a large constant, and $$c$$ is a small constant. Let the target vector be $$(k_1,\dots,k_n,cS,0,0,\dots,0)$$. Now look for the closest vector to the target, in the lattice spanned by the other vectors.