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

Question

[amk]

Допустим, есть массив

price = [11, 5, 7, 22, 54, 5, 72, 26, 30, 7, 91, 6, 8]

Нужно из него выбрать те элементы, сумма которых больше 100, к примеру, но как можно меньше больше :) Задача осложняется тем, что кол-во элементов должно быть минимальным. Как сие провернуть?

Comments

[iegor]

что значит как можно меньше больше? как можно меньше элементов? тогда это элементарный жадный алгоритм

[AtomKrieg]

Это задание, а не вопрос

Answer 1

[aRegius]

Вам, для вашей задачи, может вполне хватить функции combinations из модуля itertools. Попробуйте.

Пример для целевого числа 10:

>>> numbers = [1, 1, 1, 3, 3, 2, 2, 15, 20, 2, 1]
>>> import itertools
>>> total = []
>>> num_len = len(numbers) + 1
>>> for i in range(2, num_len):
	        num_comb = list(itertools.combinations(numbers, i))
	        total += num_comb
	
>>> total = ((i, sum(i)) for i in total if sum(i) > 10)
>>> min_total = min(total, key=lambda x: x[1])
>>> min_total
((1, 3, 3, 2, 2), 11)

Answer 2

[Sayonji]

Сложите все элементы массива (сумма S), отнимите сотню, и для полученного числа решите задачу о рюкзаке (стоимости предметов равны их весам). Получите набор элементов, в сумме ближе всего к (S - 100) снизу. Следовательно оставшиеся будут ближе всего к 100 сверху.
В решении динамическим программированием при записи максимума в очередную ячейку также записывайте минимальное количество использованных предметов.