python - 如何解决带有额外约束的背包问题？ (或替代算法)

Question

扩展背包问题的常见动态规划解决方案:

def knapSack(W, wt, val, n):
    results = []
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
    # Build tаble K[][] in bоttоm uр mаnner
    for i in range(n + 1):
        for w in range(W + 1):
            if (i == 0)  or  (w == 0):
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
    print(K[n][W])
    return(set(results))


# Driver code
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)

knapSack(W, wt, val, n) = 220

现在也许我添加额外的约束:

# Driver code
val_all = [60, 100, 120, 50, 80, 10]
wt_all = [10, 20, 30, 15, 20, 5]
W_all = 50
n_all = len(val_all)

val_1 = [60, 100, 120]
wt_1 = [10, 20, 30]
W_1 = 30
n_1 = len(val_1)

val_2 = [50, 80, 10]
wt_2 = [15, 20, 5]
W_2 = 25
n_2 = len(val_2)

我想使用相同的值最大化所有 3 个值。 val_all 的解为 240 [60, 100, 80]。 val_1 的最大值为 160 [60, 100]，val_2 的最大值为 90 [80, 10]，但考虑到我想要相同的值，并且 10 不在其他两组中，则最大解决方案将为 80。

我还想知道您是否可以添加到函数中以提供所选值以及最大值。这种方法对于大型列表是否可行，因为我有一个包含 150,000 个不同值的列表，每个值都有不同的权重。

可能有更好的算法，我的问题是我有 150,000 个值，每个值都有一个权重，需要选择任意数量的这些值，以便我们获得接近上限的 W 值。然而，该数据实际上是两种不同类型值的混合，每种类型的权重之和也有 W1 和 W2 上限值。我想最大化所有三个方程，但使用同一组值。 W1 或 W2 中选择的任何值都必须存在于 W 中。

这个背包代码不会很有用，因为我有 150k 个值，平均重量为 50，重量上限为 600 万。如此大的循环，时间复杂度将是巨大的。

Answer 1

根据最上面的评论，我发现了一个非常快并且允许这样做的包:

from mip import Model, xsum, maximize, BINARY

all = pd.read_csv('df_all.csv')
X = pd.read_csv('df_x_only.csv')
Y = pd.read_csv('df_y_only.csv')

p = all.id.values # as we arent optimizing the value of the index, p is irrelevant and we replace xsum(p[i] with xsum(w[i] in the objective function
w = all.new_weights.values
w1 = X.new_weights.values
w2 = Y.new_weights.values

c = 5876834
Cx = 4902953
Cy = 719051.4

I = range(len(w))
I1 = range(len(w1))
I2 = range(len(w2))

m = Model("knapsack")

x = [m.add_var(var_type=BINARY) for i in I]

m.objective = maximize(xsum(w[i] * x[i] for i in I)) + maximize(xsum(w1[i] * x[i] for i in I1)) + maximize(xsum(w2[i] * x[i] for i in I2))

m += xsum(w[i] * x[i] for i in I) <= c*1.05
m += xsum(w[i] * x[i] for i in I) >= c*0.95
m += xsum(w1[i] * x[i] for i in I1) <= Cx*1.05
m += xsum(w1[i] * x[i] for i in I1) >= Cx*0.95
m += xsum(w2[i] * x[i] for i in I2) <= Cy*1.05
m += xsum(w2[i] * x[i] for i in I2) >= Cy*0.95

m.optimize()


selected = [i for i in I if x[i].x >= 0.99]