Я хочу найти элементы в заданном массиве положительных целых чисел так, чтобы их сумма была меньше или равна заданному значению T. Когда оно меньше T, оно должно быть ближайшим к значению T. Я надеюсь, что это вариант задачи о сумме подмножеств в динамическом программировании.
Например, у меня есть массив A = [1, 5, 9, 11, 15] и T = 18. Ответом будет элемент 0, 1 и 3. То есть 1 + 5 + 11 = 17.
Вы можете решить это в O(NS), где S — это сумма всех элементов довольно простым способом. Хотя задача с суммой подмножества является NP-полной, вы можете кэшировать каждую полученную сумму (чтобы не вычислять повторяющиеся суммы) для решения с псевдополиномиальным временем. Простая реализация 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]
