python - 求解正整数系数的线性向量加法
问题描述
假设我有多个相同长度的不同向量
例子:
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]
其中每个值都是这些数组之一。(这只是一个随机的例子)
解决方案
你可以把你的问题写成一个线性方程组:
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]
很接近,不是吗?
这确实可能不是完美的解决方案。但是正如在这个线程中所讨论的那样“整数问题甚至都不容易解决”(@seberg)
推荐阅读
- linux - 比较用户输入的字符 x86_64 程序集
- java - 对象池使用 BaseKeyedPooledObjectFactory 问题
- ios - 上传使用 UIImagePickerController 选择的视频时遇到问题
- c# - Unity Mirror,客户端未执行损坏命令
- vue.js - 在 Vuetify 中,如何将迷你图组件放在数据表行中?
- reactjs - 带有反应路由器配置的私有和公共路由
- javascript - 使用 Oak,无需扩展即可提供 HTML?(德诺)
- node.js - 无法获取 SHOP 名称
- javascript - 我有一个 Phaser 项目,但是当我尝试加载图像时出现此错误
- c++ - 如何检查qt simple mediaplayer中是否已经存在文件