假設我有以下（總是二進制）選項：
import numpy as np
a=np.array([1, 1, 0, 0, 1, 1, 1])
b=np.array([1, 1, 0, 0, 1, 0, 1])
c=np.array([1, 0, 0, 1, 0, 0, 0])
d=np.array([1, 0, 1, 1, 0, 0, 0])
而且我想找到上述的最佳組合，至少讓我達到最低限度：
req = np.array([50,50,20,20,100,40,10])
例如：
final = X1*a X2*b X3*c X4*d
- 這是否映射到一個已知的運籌學問題？還是它屬于數學規劃？
- 這是 NP 難的，還是在合理的時間內完全可以解決的（我假設它是不可能完全解決的）
- 有知道的解決方案嗎？
注意：陣列的實際長度更長——想想~50，選項的數量~20
uj5u.com熱心網友回復：
這是一個覆寫問題，可以使用整數程式求解器輕松解決（我在下面使用了 OR-Tools）。如果 X 變數可以是小數，則替換NumVar為IntVar。如果 X 變數為 0--1，則替換為BoolVar.
import numpy as np
a = np.array([1, 1, 0, 0, 1, 1, 1])
b = np.array([1, 1, 0, 0, 1, 0, 1])
c = np.array([1, 0, 0, 1, 0, 0, 0])
d = np.array([1, 0, 1, 1, 0, 0, 0])
opt = [a, b, c, d]
req = np.array([50, 50, 20, 20, 100, 40, 10])
from ortools.linear_solver import pywraplp
solver = pywraplp.Solver.CreateSolver("SCIP")
x = [solver.IntVar(0, solver.infinity(), "x{}".format(i)) for i in range(len(opt))]
extra = [solver.NumVar(0, solver.infinity(), "y{}".format(j)) for j in range(len(req))]
for j, (req_j, extra_j) in enumerate(zip(req, extra)):
solver.Add(extra_j == sum(opt_i[j] * x_i for (opt_i, x_i) in zip(opt, x)) - req_j)
solver.Minimize(sum(extra))
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
print("Solution:")
print("Objective value =", solver.Objective().Value())
for i, x_i in enumerate(x):
print("x{} = {}".format(i, x[i].solution_value()))
else:
print("The problem does not have an optimal solution.")
輸出：
Solution:
Objective value = 210.0
x0 = 40.0
x1 = 60.0
x2 = -0.0
x3 = 20.0
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505872.html
上一篇：高效線段-三角形相交
下一篇：用于對齊128塊中的數字的公式