Блог

Главная - Вопросы по программированию - Алгоритм для нахождения первой суммы массива в пределах диапазона

Алгоритм для нахождения первой суммы массива в пределах диапазона

#c# #algorithm

#c# #алгоритм

Вопрос:

У меня довольно сложный (для меня) алгоритм, который я пытаюсь написать. Идея состоит в том, чтобы определить, какие элементы в массиве суммируются первыми до значения, попадающего в диапазон.

Например:

У меня есть массив [1, 15, 25, 22, 25] , который находится в приоритетном порядке.

Я хочу найти первый набор значений с наибольшим количеством элементов, сумма которых находится в пределах минимального и максимального диапазона, не обязательно тот набор, который приближает меня к моему максимуму.

Итак, если min равно 1, а max равно 25, я бы выбрал [0(1), 1(15)] , даже если третий элемент [2(25)] ближе к моему максимальному значению 25, потому что они стоят на первом месте.

Если min равно 25, а max равно 40, я бы выбрал [0(1), 1(15), 3(22)] , пропустив третий элемент, поскольку это нарушило бы max.

Если min равно 50, а max равно 50, я бы выбрал [2(25), 4(25)] , поскольку это единственные два, которые могут соответствовать минимальным и максимальным требованиям.

Существуют ли какие-либо общие алгоритмы CS, соответствующие этому шаблону?

Комментарии:

1. Точная цель мне несколько неясна. В первом случае почему бы просто не взять [0(1)] ? Во втором случае, почему бы не взять [2(25)] или [0(1), 2(25)] или [1(15), 2(25)]?

2. Я добавил уточнение. Я также хочу получить наибольшее количество элементов. Поэтому, даже если предположить, что первый элемент удовлетворяет min / max, я хочу продолжать считать, чтобы получить наибольшее количество элементов в параметрах.

3. Итак, вы хотите найти наибольшее подмножество элементов в вашем списке таким образом, чтобы их сумма попадала в заданный диапазон.

4. Правильно, но фишка в том, что это должен быть «первый» набор. Это означает, что я бы взял набор из 2 элементов, которые попадают в диапазон, вместо набора из 3 элементов, если бы набор из 2 был ближе к началу массива.

5. для первого примера почему бы и нет [0(1), 3(22)] ответ? Он удовлетворяет min, max лучше, чем [0(1), 1(15)]

Ответ №1:

Это проблема динамического программирования.

Вы хотите построить структуру данных, чтобы ответить на следующий вопрос.

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

Когда он находит target_sum в диапазоне, вы просто перечитываете его, чтобы получить ответ.

Вот псевдокод для этого. Я использовал слегка Pythonish синтаксис и 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 .

Метки: