2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Выделение предельных подмножеств - где найти алгоритмы ?
Сообщение15.03.2009, 16:22 
Всем привет.
Имеется множество чисел: S= {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

Требуется найти все его подмножества (порядок элементов внутри них неважен), сумма элементов которых меньше 20, но при этом добавление к ним любого другого элемента из исходного S приведет к тому, что сумма станет >= 20.
Например, это будут такие наборы: {1,2,3,4,9}, {1,2,3,5,8}, {1,2,3,5,7}, {1,2,3,5,6} и т.д.

Вопрос: где найти описание эффективных алгоритмов, дающих на выходе такие наборы ?

 
 
 
 
Сообщение15.03.2009, 16:31 
Аватара пользователя
Эта задача очень похожа на задачу о рюкзаке
http://en.wikipedia.org/wiki/Knapsack_problem
http://ru.wikipedia.org/wiki/Задача_о_ранце
Задача NP-трудная, так что любой алгоритм, который выдает все такие наборы, существенно переборный.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group