ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sanito                               2:5020/400     05 May 2003  19:58:19
 To : All
 Subject : Вычисление максимально приближенной суммы
 -------------------------------------------------------------------------------- 
 

 Добрый день всем!
 
 Вот такая задачка... Есть N чисел (для облегчения пусть
 это будут целые числа). Дано некоторое число K, необходимо
 найти любую (первую) последовательность без повторяющихся
 элементов (сами значения цифр могут совпадать), сумма
 которых равна K (в идеале - максимально близка на некоторую
 фиксированную дельту).
 
 Я сделал так (просто алгоритм перебором):
 1. Установить первый бит битового массива размерности N в 1
 2. Выполнять прибавление единицы до тех пор, пока массив не
 будет заполнен полностью единицами.
 3. Hа каждой итерации считать сумму чисел, в позициях которых
 взведены биты и сравнивать ее с искомой, постепенно приближаясь,
 если очередная сумма ближе к искомой.
 
 Такой алгоритм имеет сложность O(2^^N), что на N = 69 уже
 является полной торбой...
 
 Что посоветуете?
 
 С уважением,
 Александр Почечуев.
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор