Выборка чисел

[uber]

Есть задача:
1. существует последовательность чисел: 3.5; 2.0; 1.5; 0,8; 5.0; 4.1; 3.5 (например. их может быть больше и могут повторяться)
их отсортировать (это я сделал).
2. организовать выборку чтобы выбирались числа в сумме как можно близкие к 6.0, сдагаемых может быть сколько угодно (5.0+0.8 например, но не больше 6,0)

данные считывал из StringGrid, но никак не получилось сделать переход от ячейки к ячейки с учетом возожности повторения чисел.

есть варианты?

[Serge_Bliznykov]

тему, имхо, не там создали - надо было в Помощь
только перебор..
а в сумме всегда два слагаемых или может быть три и больше? (3.5+2+0.8 = 6.3)

[ds.Dante]

Я услышал впервые эту задачу где-то лет в 14. Проблема в том, что скорость алгоритма - O(2^n), и начиная где-то с 25 чисел перебор идёт очень долго. Мне пришла в голову идея на каждом шаге прибавлять или вычитать только одно число, но как это реализовать я не догодался. И только год назад я прочитал про код Грея. Я заново написал программу, критический участок написал на ассемблере... и программа стала в полтора раза быстрее. :) То есть задачу я так и не решил.

Про код Грея можно почитать в книге "Алгоритмические трюки для программистов (Генри Уорен мл.)".

[LeBron]

Нда...Эта задача волнует не только Вас. Над ней многие сейчас голову ломают. Задача о рюкзаке... Вроде бы уже доказали, что она не имеет полного полиномиального решения для случайных неопределенных наборов данных... Но этого я с увереностью сказать не могу, надо в англоязычной части сети гуглить. Могу только с увереностью сказать, что полного полиномиального решения пока не известно.
Есть псевдополиномиальные решения, например, если конечно количество возможных сум, то можно решить за линейное время с заданным коефициентом. Есть решения, которые работают полиномиально, но дают верный ответ лиш с некоторой вероятностью.
З.Ы. Я тут подумал, задача немного упрощена относительно класического рюкзака, легко понять, как решать динамикой. Только не по перечисляему типу, а по множеству разбиений. Тоесть первый доступный вес - 0, дальше все веса, которые можно получить плюсированием к нулю, дальше все, которые можно получить плюсированием к полученым ранее. Только решение очень нестойкое, фактически оно привязано к количеству возможных сум, тоесть будет быстро работать для многих случаев, но все же псевдополиномиально, так как часто котиться до 2^N.

[Serge_Bliznykov]

замечательное обсуждение получилось!

Uber, а объясните мне, что означает Ваша фраза

Сообщение от Uber

с учетом возожности повторения чисел.

???

[uber]

с учетом возожности повторения чисел.

это значит, например, 3.5 может встречаться в ряде чисел несколько раз.

а если, все числа отсортировать на:
0<x<=1
1<x<=2
2<x<=3
3<x<=4
4<x<=5
5<x<=6
и перебирать сумму из соответствующих столбцов:
напрмер:

(5<Х<=6) + (0<x<=1) =<6 (допустим 5,1 + 0,8 = 5,9)

и так далее...

или слишком много условий и циклов будет?

[Serge_Bliznykov]

uber, ясно, а я уж решил, что число можно несколько раз использовать...

Вы не ответили - Вас интересует сумма только (и строго) ДВУХ чисел?!
Если да - то несложный перебор позволит быстро решить задачу. (практически при любом количестве исходных чисел).

и ещё, если равнозначных вариантов несколько - выдавать все? или первого достаточно?

[uber]

слагаемых может быть несколько.
выдаются все суммы:
5,1+0,8=5,9
4,0+1,0+0,8+0,1=5,9
3,5+2,2=5,7
например...
главное чтобы сумма была как можно ближе к 6,0, но не больше
на печать идет лучший варинат, с наибольшим количеством задействованных элементов...


))
я как раз пробую делать вот так:
сортирую по значению
0<x<=1
1<x<=2
2<x<=3
3<x<=4
4<x<=5
5<x<=6
и перебирать сумму из соответствующих столбцов:
напрмер:

(5<Х<=6) + (0<x<=1) =<6 (допустим 5,1 + 0,8 = 5,9)

[Serge_Bliznykov]

слагаемых может быть несколько.

тогда дело швах... ;(
только ПОЛНЫЙ перебор ВСЕХ ВОЗМОЖНЫХ сочетаний.
и даже то, что можно сразу переходить к следующему варианту, как только сумма варианта стала > ТребуемыйЛимит - НЕ СПАСАЕТ ситуацию.

когда то давно я писал для себя программку (FilesSizeSumator), которая подбирает оптимальное заполнение файлами CD-диск. Так вот, если входных значений 12 или меньше - то всё работает в приемлемые сроки, но большее число элементов обрабатывать нереально... посмотрите, вверху ds.Dante писал. Это всё так. Только приемлимое количество чисел сильно зависит от реализации...
грубо говоря. пусть программа перебирает 10 чисел за 1 минуту. Но тогда (очень приблизительно, но порядок верен) 11 чисел будет обработано за 11 минут. 12 чисел за 132 минуты и т.д. мысль понятна?
Ускорить можно вводя ограничения на количество слагаемых или убрать требование на нахождение наилучшего варианта (ввести необходимую погрешность Epsilon - как только сумма < Требуемый_лимит и сумма >= Требуемый_лимит - Epsilon — сразу прерывать перебор..

желаю удачи.

p.s. а если не секрет, для чего Вы решаете эту задачу? Какое практическое/прикладное назначение?...

[uber]

это всё логично...а разве если все элементы разбить по интервалам:
0<X<=1 ........ 5<X<6
и перебирать сумму с элементами только из определенных столбцов??
если 0<X<=1 (пусть 0,75) и 4<X<=5 (пусть 4,9), то логично что 0,75+4,9<>6 ? а дальше

{6-(0,75+4,9)=0.35}
if {поиск среди всех элементов X=0.35} then Summ:={4.9+0,75+0,35}
else {если не нашел, то переходит к другим элементам}

и ввессти Epsilon


П.С.
да, это задача у меня сама собой родилась в голове из ее рабочей необходимости решения.. надоело ) подбирать такую сумму собственной головой, пусть компьютер считает..
то варинатов куча..это меня сразу насторожило.