58
правок
Изменения
→Задача о суммах подмножеств
==Задача о суммах подмножеств==
'''Задача о суммах подмножеств''' (англ. ''Subset-sum problem, Value Independent Knapsack Problem'') - задача из семейства, в которой стоимость предмета совпадает с его весом.
'''Пример:''' В машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
===Формулировка Задачи===
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Более формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы
