2

I'm sorry for my ignorance; I don't even know the correct terminology or proper way to phrase my question. I tried searching but require human assistance. I'm sorely deficient in understanding of basic math and will have to illustrate.

Here's a simple example. Let's say I have the following numerical arrays:

array A: [6,1]

array B: [2,7]

array C: [58,123]

....and I want to find a ratio of A to B which, summed, will result in array C. In this case, I know the answer is 4:17:

4*[6,1] = [24,4]

17*[2,7] = [34,119]

[24,4] + [34,119] = [58,123]

....but I have no idea how to derive that without guesswork, which in my application of this problem will be inadequate because there will be hundreds of arrays, each containing hundreds of numbers. There will usually be multiple possible answers: only one need be found. In some cases there will be no possible answer: the ratio that comes "closest" will be needed then, but that's a whole different animal.

Anonymous
  • 21

2 Answers2

1

How about the following method. Instead of $A = (6,1)$ and $B = (2,7)$, let's consider $A' = A - 3B = (0,-20)$ and $B$. To know how many $A'$ and $B$ we need to get $C = (58,123)$, we might notice that the first coordinate $58$ comes only from our $B$. So we get $29B$. The rest will be $A'$. $29(7) = 203$, and so $123 - 203 = -80$. This happens to be exactly $4$ times the second coordinate of $A'$, so we see that $C - 29B = 4A'$, or rather that $C = 29B + 4A'$.

Of course, $A' = A - 3B$, so that $C = 29B + 4A' = 29B + 4A - 12B = 4A + 17B$, just as you said.

In fact, I claim that this general process will always work, and will always yield the correct (and in this case, unique) answer, or will show that such a thing is impossible. In a class involving some linear algebra, the method I've espoused is called Gaussian Elimination or row reduction (when viewed in the right way).

Finally, you speak of the 'closest ratio' - that sounds like a particular 'projection' of the 'desired vector' onto the vector space formed by your $A,B$ vectors (to use google-able words) - unless you want only integer multiples of vectors. Then it's really hard, and sounds strictly harder to compute than the Knapsack Problem.

davidlowryduda
  • 91,687
0

I assume you are familiar with vectors and matrices. Instead of arrays, a more nicer word is vectors in your case. Let me try to use your example. \begin{align} A=\begin{bmatrix}6 \\ 1\end{bmatrix}\\ B=\begin{bmatrix}2 \\ 7\end{bmatrix}\\ C=\begin{bmatrix}58 \\ 123\end{bmatrix} \end{align} You wanted two numbers $x_1$ and $x_2$ such that \begin{align} x_1\begin{bmatrix}6 \\ 1\end{bmatrix}+x_2\begin{bmatrix}2 \\ 7\end{bmatrix}=\begin{bmatrix}58 \\ 123\end{bmatrix} \end{align} This you can rewrite as \begin{align} \begin{bmatrix}6 & 2 \\ 1 & 7\end{bmatrix}\begin{bmatrix}x_1 \\ x_2\end{bmatrix}=\begin{bmatrix}58 \\ 123\end{bmatrix} \end{align} Now you need to solve for $x_1$ and $x_2$. See $A$ and $B$ stacks as the columns of the matrix on the left side. This is the so called Linear System of Equations and the majority of Linear algebra is to learn how to solve this. When you have several vectors as you mentioned, you can stack them as columns of the matrix on the left side and then you solve the Linear System of Equations. As mentioned by the other user, gaussian elimination is a prominent technique for that. If you are familiar with matrix inversion, that will give another technique but costly one. All of this will be available to learn from a standard linear algebra textbook.

dineshdileep
  • 8,887