c# - Algorithm to find first sum of an array within a range

Question

I'm have a fairly complicated (to me) algorithm that I'm trying to write. The idea is to determine which elements in an array are the first ones to sum up to a value that falls within a range.

For example:

I have an array [1, 15, 25, 22, 25] that is in a prioritized order.

I want to find the first set of values with the most elements that sum within a minimum and maximum range, not necessarily the set that get me closest to my max.

So, if the min is 1 and max is 25, I would select [0(1), 1(15)] even though the third element [2(25)] is closer to my max of 25 because those come first.

If the min is 25 and max is 40, I would select [0(1), 1(15), 3(22)], skipping the third element since that would breach the max.

If the min is 50 and max is 50, I would select [2(25), 4(25)] since those are the only two that can meet the min and max requirements.

Are there any common CS algorithms that match this pattern?

question from:https://stackoverflow.com/questions/65938207/algorithm-to-find-first-sum-of-an-array-within-a-range

Answer 1

This is a dynamic programming problem.

You want to build a data structure to answer the following question.

by next to last position available in the array:
    by target sum:
        (elements in sum, last position used)

When it finds a target_sum in range, you just read back through it to get the answer.

Here is pseudocode for that. I used slightly Pythonish syntax and JSON to represent the data structure. Your code will be longer:

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)

This will return the desired values rather than the indexes. To switch, just reverse what goes into the answer.