Как найти элементы в массиве, сумма которых равна или меньше и ближе к заданному значению?

Question

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

Например, у меня есть массив A = [1, 5, 9, 11, 15] и T = 18. Ответом будет элемент 0, 1 и 3. Это 1 + 5 + 11 = 17.

Answer 1

Вы можете решить это в O(NS), где S - сумма всех элементов довольно простым способом. В то время как задача с суммой подмножеств является NP-Complete, вы можете кэшировать каждую сумму, которую вы делаете (так что вы не рассчитываете повторные суммы) для решения с псевдополиномиальным временем. Простая реализация python выглядит следующим образом. Это вернет минимально возможную сумму:

def solve(arr, T):
    # the size of this set is bounded by S
    possible_sums = set()
    for i in arr:
        # incorporate sums from adding i to each already seen subset
        possible_sums |= {i + s for s in possible_sums}
        # just i is an additional possible subset
        possible_sums.add(i)
    # return the greatest <= T
    return max(s for s in possible_sums if s <= T)

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

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

def solve(arr, T):
    # dictionary in the form of sum: last_index_added
    possible_sums = {}
    records = []
    # do the same as before but remember the last index
    for i in range(len(arr)):
        possible_sums = {**possible_sums, **{arr[i] + s: i for s in possible_sums}}
        possible_sums[arr[i]] = i
        records.append(possible_sums)

    # find the best sum and retrace our steps on how we got here
    best_sum = max(s for s in possible_sums if s <= T)
    record_idx = len(arr) - 1
    res = []
    while best_sum:
        last_idx = records[record_idx][best_sum]
        res.append(last_idx)
        best_sum -= arr[last_idx]
        record_idx = last_idx - 1
    return res

Контрольный пример:

>>> print(solve([1, 5, 9, 11, 15], 18))
[3, 1, 0]