Given n 3D vectors e_i, 1 <= i <= n, and a 3D vector vector v, find the value of the coefficients c_i such that v is described as a linear combination of the n vectors
v = c_0*e_0 + c_1*e_1 + ... + c_n*e_n
but the twist is to calculate c_i such that abs(c_i) <= a_i, where a_i will be given, 1 <= i <= n.
Print the coefficients c_i or print that it's impossible. (If possible print the answer that minimizes the sum of c_i). I have been pondering this question for quite some days and I still have zero idea how to approach this, will it be DP or greedy with some heuristics. I did not add any constraints since I don't really know what the time complexity will be. Any help will be appreciated. Thank you.
This problem can be formulated as a linear programming task:
We aim to find coefficients
c_isuch thatv = c₀·e₀ + c₁·e₁ + ... + cₙ₋₁·eₙ₋₁
with constraints |cᵢ| ≤ aᵢ, and minimize the objective S = c₀ + c₁ + ... + cₙ₋₁.
This fits well into the standard LP form: - The objective is linear (minimize the sum of
cᵢ), - There are equality constraints to match all 3 coordinates ofv, - And bounds:-aᵢ ≤ cᵢ ≤ aᵢ.We can solve it using
scipy.optimize.linprog(with HiGHS method). The matrix of constraints is just the transpose of the list of 3D vectors.If
linprogreturns a valid solution under the given bounds, we print the coefficients; otherwise, it's impossible.You are right, linear programming will work in this problem. If i make a struct to store vectors and put the values in the simplex algorithm, it would be sufficient for my case. Thanks a lot.