链接存储桶的最佳组合

Question

假设我有以下(总是二进制(选项：

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

1. 这是否映射到已知的运筹学问题？或者它属于数学编程
2. 这个NP很难，或者在合理的时间内完全可以求解(我假设它在组合上不可能精确求解(
3. 有已知的解决方案吗

注意：数组的实际长度更长-想想大约50个，选项的数量大约20个我目前的研究使我找到了一些任务问题和背包的结合，但不太确定。

Answer 1

这是一个覆盖问题，使用整数程序求解器很容易解决(我在下面使用了OR工具(。如果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