Алгоритм выбора N предметов по цене? День добрый, уважаемые)
Столкнулся с такой задачей:
Например, у нас есть 4 предмета(может быть сколько угодно) и их цена
1 - 5p
2 - 10p
3 - 5p
4 - 10p
Задача стоит такая, выбрать отсюда предметы таким образом, чтобы они удовлетворяли условию: сумма выбранных предметов = 30%(+-5% (например) от общей суммы предметов.
В данном случае возможны такие комбинации: 1,3 и 2. ( В приоритете комбинация с меньшим кол-ов предметов)
Т.е нужно получить максимально близкую к N% от общей суммы комбинацию предметов.
Кто нибудь сталкивался с подобными алгоритмами?
Есть примеры решения/алгоритмов?
Предполагаю, что сначала нужно построить все сочетания без повторений, и из них уже выбрать наиболее подходящее сочетание?

Предыдущий
вопрос Следующий
вопрос

Да, вы правильно предположили. Для решения данной задачи можно воспользоваться методом перебора всех возможных сочетаний предметов и выбрать из них ту комбинацию, которая наиболее близка к заданному проценту от общей суммы.

Примерный алгоритм решения задачи:

Создать функцию, которая будет генерировать все возможные комбинации предметов без повторений.Для каждой комбинации вычислить сумму цен выбранных предметов.Выбрать из всех комбинаций ту, которая наиболее близка к заданному проценту от общей суммы предметов (например, 30%).Вывести выбранную комбинацию предметов.

Примерный код на Python:

from itertools import combinations
items = {
1: 5,
2: 10,
3: 5,
4: 10
}
target_percentage = 0.3
target_sum = sum(items.values()) * target_percentage
best_combination = None
best_diff = float('inf')
for i in range(1, len(items) + 1):
for comb in combinations(items.keys(), i):
sum_comb = sum(items[item] for item in comb)
if abs(sum_comb - target_sum) < best_diff:
best_combination = comb
best_diff = abs(sum_comb - target_sum)
print(best_combination)

Этот код будет выводить наилучшую комбинацию предметов, которая будет наиболее близка к 30% от общей суммы предметов. Вы можете изменить значение target_percentage на нужный вам процент.