Учитывая один (1xN) список положительных весов (не обязательно целые числа, т.е. числа с плавающей запятой) и список соответствующих затрат равной длины (1xN), я хочу найти подмножество списка весов, которое суммируется точно с заданной суммой S и имеет наименьший стоимость (сумма затрат * веса, соответствующие подмножеству в списке весов). Лучше всего было бы написать на Python (если это возможно), так как я не очень хорошо разбираюсь в других языках!
Пример:
w = [2.5, 3.0, 1.0, 5.5] # Weight list
c = [1.0, 1.5, 2.0, 3.0] # Cost list
S = 6.5 # Target sum
Для этого случая у нас есть два возможных подмножества, которые в сумме дают S:
sub1 = [2.5, 3.0, 1.0]
sub2 = [1.0, 5.5]
Затраты на эти подмножества составляют:
cost1 = 2.5*1.0+3.0*1.5+1.0*2.0 = 9.0
cost2 = 1.0*2.0+5.5*3.0 = 18.5
Поскольку подмножество 1 имеет наименьшую стоимость (9,0), мне нужно именно это подмножество.
Одно из возможных решений, конечно, состоит в том, чтобы рассчитать все возможные комбинации, а затем просто выбрать минимум рассчитанных затрат. Я надеялся, что есть более эффективное решение этой проблемы.
Я искал разные решения, но я мог найти только решения для Python, которые решают проблему равной суммы и одновременно не получают наименьшую стоимость. Вот пример такого решения: Certain-Number">Алгоритм поиска числа в списке, которое в сумме дает определенное число.
