求解正整数系数的线性向量加法

Question

假设我有多个相同长度的不同向量

示例：

1: [1, 2, 3, 4]
2: [5, 6, 7, 8]
3: [3, 8, 9, 10]
4: [6, 9, 12, 3]

我想找出这些向量的最佳整数系数，使向量之和最接近各自指定的目标向量。

目标向量：[55,101,115,60]

假设组合只涉及将数组加在一起（没有减法），我将如何做呢？是否有任何 Python 库（numpy、scikit 等）可以帮助我做到这一点？我怀疑是线性代数解

示例组合答案：[3, 3, 3, 1, 2, 4, 1, 1, 1, 2, 3, 4] 其中每个值都是这些数组之一。（这只是一个随机示例）

Answer 1

您可以将问题写成线性方程组：

arr1[0] + b*arr2[0] + c*arr3[0] + d*arr4[0] = res[0]
a*arr1[1] + b*arr2[1] + c*arr3[1] + d*arr4[1] = res[1]
a*arr1[2] + b*arr2[2] + c*arr3[2] + d*arr4[2] = res[2]
a*arr1[3] + b*arr2[3] + c*arr3[3] + d*arr4[3] = res[3]
#For all positive a,b,c,d.

如果有精确解，你可以求解。

如果没有精确解，有一种scipy方法可以计算线性矩阵方程的非负最小二乘解，称为scipy.optimize.nnls。

from scipy import optimize
import numpy as np

arr1 = [1, 2, 3, 4]
arr2 =  [5, 6, 7, 8]
arr3 = [3, 8, 9, 10]
arr4 = [6, 9, 12, 3] 

res = [55,101,115,60]

a = np.array([
    [arr1[0], arr2[0], arr3[0], arr4[0]],
    [arr1[1], arr2[1], arr3[1], arr4[1]],
    [arr1[2], arr2[2], arr3[2], arr4[2]],
    [arr1[3], arr2[3], arr3[3], arr4[3]]
])

solution,_ = optimize.nnls(a,res)

print(solution)

print('Coefficients before Rounding', solution)
solution = solution.round()
print('Coefficients after Rounding', solution)
print('Resuls', [arr1[i]*solution[0] + arr2[i]*solution[1] + arr3[i]*solution[2] + arr4[i]*solution[3] for i in range(4)])

这将打印

Coefficients before Rounding [0.         0.1915493  3.83943662 6.98826291]
Coefficients after Rounding [0. 0. 4. 7.]
Resuls [54.0, 95.0, 120.0, 61.0]

很接近，不是吗？

这确实不是完美的解决方案。但正如 this thread 中所讨论的那样，“解决整数问题甚至都不容易” (@seberg)

求解正整数系数的线性向量加法

Solving linear vector addition for positive integer coefficients

python

arrays

numpy

linear-algebra