假设您连续获得 20 个随机数。必须保持原来的顺序。从此组中，您可以选择 2 组，每组 3 个号码。这些组的位置必须至少用 4 个数字隔开。
目标是最大化两个组中的值的总和。您如何确保选择最佳组？
主要问题是选择第一组的规则可能会由于约束条件而恶化第二组的选择。最佳解决方案可能会排除“最佳”单个组。
对于任何大小的原始集、组的大小、组的数量和约束的长度，一般有什么方法可以解决这个问题？
在集合中选择最高值的非相邻组
计算科学
约束优化
2021-12-28 05:54:12
2个回答
这是原始问题的强力二次解法，原始问题的线性解法，以及三组的强力法和通用线性解法。
import numpy as np
N = 20
G = 3
MINSEP = 4
def solve_cubic(a):
r = range(N - G + 1)
return max(
(
(a[i:i+G]+a[j:j+G]+a[k:k+G]).sum(), i, j, k
) for i in r for j in r for k in r if (
i + G + MINSEP <= j and j + G + MINSEP <= k))
def solve_quadratic(a):
r = range(N - G + 1)
return max(
(a[i:i+G].sum() + a[j:j+G].sum(), i, j) for i in r for j in r if (
j-i > G+MINSEP-1))
def solve_linear(a):
sumc = np.cumsum(a)
sumc = np.array([0] + sumc.tolist())
sumg = sumc[G:] - sumc[:-G]
rmax = np.maximum.accumulate(sumg[::-1])[::-1]
scores = sumg[:-(MINSEP+G)] + rmax[(MINSEP+G):]
i = np.argmax(scores)
j = i + MINSEP + G + np.argmax(sumg[i + MINSEP + G:])
return scores[i], i, j
def solve_linear_generic(numbers, groups):
sumc = np.cumsum([0] + list(numbers))
sumg = sumc[G:] - sumc[:-G]
table = {}
trace = {}
for a in range(N - G + 2):
a_prime = a - MINSEP - G
for b in range(groups + 1):
if a == 0:
table[a, b] = 0 if b == 0 else -1
trace[a, b] = ()
else:
c0 = table[a-1, b]
tracec0 = trace[a-1, b]
if b == 0:
table[a, b] = c0
trace[a, b] = tracec0
else:
c1 = sumg[-a]
tracec1 = (N - G + 1 - a,)
if a_prime >= 0:
c1 += table[a_prime, b-1]
tracec1 = tracec1 + trace[a_prime, b-1]
if c0 < c1:
table[a, b] = c1
trace[a, b] = tracec1
else:
table[a, b] = c0
trace[a, b] = tracec0
return (table[N - G + 1, groups],) + trace[N - G + 1, groups]
def main():
a = np.random.randint(100, size=N)
print a
print 'two groups:'
print solve_quadratic(a)
print solve_linear(a)
print solve_linear_generic(a, 2)
print 'three groups:'
print solve_cubic(a)
print solve_linear_generic(a, 3)
main()
如果我正确理解您的问题，您可以将其写为以下整数优化问题：让是两组三个数字的起始索引，那么你要解决
像所有整数优化问题一样，可能很难找到确切的答案。另一方面，如果您允许数字数组变大
其它你可能感兴趣的问题