我有一个相当复杂的(对我来说)算法，我想写。其思想是确定数组中哪些元素首先求和得到一个在一定范围内的值。
例如:
我有一个按优先顺序排列的数组[1, 15, 25, 22, 25]。
我想找到第一个在最小和最大范围内和的元素最多的值的集合，不一定是最接近最大值的集合。
所以，如果最小值是1，最大值是25，我会选择[0(1), 1(15)]，即使第三个元素[2(25)]更接近我的最大值25，因为它们在前面。
如果最小值是25，最大值是40，我将选择[0(1), 1(15), 3(22)]，跳过第三个元素，因为这会破坏最大值。
如果min是50,max是50，我会选择[2(25), 4(25)]，因为这是唯一两个可以满足min和max要求的。
是否存在与此模式匹配的通用CS算法?
这是一个动态规划问题。
你想构建一个数据结构来回答下面的问题。
by next to last position available in the array:
by target sum:
(elements in sum, last position used)
当它在range中找到target_sum时，只需回读它以获得答案。
这里是伪代码。我使用了一些python语法和JSON来表示数据结构。你的代码会更长:
Initialize the lookup to [{0: (0, null)}]
for i in 1..(length of array):
# Build up our dynamic programming data structure
Add empty mapping {} to end of lookup
best_sum = null
best_elements = null
for prev_sum, prev_elements, prev_position in lookup for i-1:
# Try not using this element
if prev_sum not in lookup[i] or lookup[i][prev_sum][0] < prev_elements:
lookup[i][prev_sum] = (prev_elements, prev_position)
# Try using this element
next_sum = prev_sum + array[i-1]
next_elements = prev_elements + 1
prev_position = i-1
if next_sum not in lookup lookup[i][next_sum][0] < prev_elements:
lookup[i][next_sum] = (next_elements, next_position)
if next_sum in desired range:
if best_elements is null or best_elements < this_elements
best_elements = this_elements
best_sum = this_sum
if best_elements is not null:
# Read out the answer!
answer = []
j = i
while j is not null:
best_sum = lookup[j][0]
answer.append(array[j])
j = lookup[j][1]
return reversed(answer)
这将返回所需的值而不是索引。要切换，只需反转进入answer的内容。