Существуют ли алгоритмы ?

← →
de. (2008-02-13 10:23) [0]

Здравствуйте уважаемые мастера !
У меня к вам вопрос:
Существуют ли алгоритмы нахождения во множестве чисел такой суммы, которая бы была ровна сумме нескольких элементов этого множества ?

Поясняю:
Есть множество:
(435, 6473, 64, 6, 67376, 54, 77, 345)

И есть некая сумма, полученная не из этого множества

73903

необходимо во множестве найти такие элементы которые могут давать эту сумму . (435, 6473, 64, 6, 67376, 54, 77, 345)

причем сумму могут давать несколько элементов множества....

Очень нужна помощь, Заранее огромное спасибо !

← →
DrPass © (2008-02-13 10:23) [1]

Существуют, конечно. Называется "алгоритм полного перебора"

← →
de. (2008-02-13 10:28) [2]

> DrPass © (13.02.08 10:23) [1]

А как он реализовывается ?

← →
shlst (2008-02-13 10:29) [3]

если это что бы диски полнее записывать разными файлами, а искать потом эти файлы через программу каталогизатор, то это образец как старается стать эффективной система, у которой цели другие, нежели рентабельность - например цель больше рабочих мест.

---
включите меня включите

← →
de. (2008-02-13 10:37) [4]

Нет это отчет. Просто цифру ищу. Из чего она слаживалась.
Кто может привести пример на этого алгоритма на Delphi ?

← →
Johnmen © (2008-02-13 10:42) [5]

Задачи, которые ставит преподаватель, каждый решает сам.
Если не может, то платит деньги.

← →
de. (2008-02-13 10:47) [6]

Ладно все с вами ясно...

З.Ы.

> Нет это отчет. Просто цифру ищу. Из чего она слаживалась.

← →
Рамиль © (2008-02-13 10:53) [7]

> de. (13.02.08 10:47) [6]

С тобой то же.

← →
Iam (2008-02-13 10:55) [8]

de. (13.02.08 10:47) [6]
рекурсивно или итеративно

← →
TUser © (2008-02-13 10:57) [9]

Это дискретная задача о рюкзаке только с дополнительным условием, - надо проверить, что рюкзак набился под завязку. Она NP-полная, то есть точных и достаточно быстрых алгоритмов нет. Если числе мало, как у тебя в примере, то решается перебором, а если числе много (ну, скажем, сотни), то надо искать эвристики.

← →
de. (2008-02-13 11:11) [10]

> DrPass © (13.02.08 10:23) [1]

> shlst (13.02.08 10:29) [3]

> Iam (13.02.08 10:55) [8]

> TUser © (13.02.08 10:57) [9]

Спс.

← →
de. (2008-02-13 11:26) [11]

> > DrPass © (13.02.08 10:23) [1]
>
>
> > shlst (13.02.08 10:29) [3]
>
>
> > Iam (13.02.08 10:55) [8]
>
>
> > TUser © (13.02.08 10:57) [9]

Сколько будет WMR стоить, реализация данного алгоритма ?
ТЗ:

Ввод элементов множества, всего их может быть 1 до 300.
Ввод числа, которое должно быть равно сумме элементов множества, или второй вариант: максимально равно этому числу. (максимально приближенное.)
Вывод этих самых элементов которые дают такую сумму.

Все числа целые, использовать наверное лучше динамический массив как множество.

?

← →
de. (2008-02-13 11:26) [12]

> реализация данного алгоритма ?

на Delphi

← →
Iam (2008-02-13 11:27) [13]

de. (13.02.08 11:26) [11]
деньги вперёд зачислишь?70%, 30% после работы

← →
de. (2008-02-13 11:29) [14]

> Iam (13.02.08 11:27) [13]

Гы. скока ?

← →
de. (2008-02-13 11:34) [15]

Вот еще может кому поможет.

http://algolist.manual.ru/maths/combinat/permutations.php
http://olddesign.isu.ru/~slava/teach/school/comb_red.htm#pruning
http://olddesign.isu.ru/~slava/teach/school/comb_ret.htm
http://www.forum.mista.ru/topic.php?id=6376
http://www.rulibrary.com/book-101-38.html

Сам бы взялся да сообразить не могу, в реализации алгоритма еще работы куча...

← →
Iam (2008-02-13 11:36) [16]

de. (13.02.08 11:29) [14]
165

← →
de. (2008-02-13 11:39) [17]

Условие такое:
В программе делается например Edit где элементы указываются через запятую.
Ниже Edit в котором указывается число которому должна соответствовать (или максимально соответствовать) сумма найденых элементов.
Еще ниже ListBox в котором отображаются элементы дающие эту самую сумму.

← →
de. (2008-02-13 11:40) [18]

> Iam (13.02.08 11:36) [16]
> de. (13.02.08 11:29) [14]
> 165

Чего побаюсь спросить... :o)

← →
de. (2008-02-13 11:45) [19]

> Iam (13.02.08 11:36) [16]

Если 165 руб. то могу 500 руб. предложить. Но при условии что алгоритм будет работать правельно.

← →
de. (2008-02-13 11:49) [20]

Вот еще http://www.yandex.ru/yandsearch?text=%C0%EB%E3%EE%F0%E8%F2%EC+%EF%EE%EB%ED%EE%E3%EE+%EF%E5%F0%E5%E1%EE%F0%E0&rpt=rad

← →
de. (2008-02-13 11:54) [21]

Ау. если фактически эта тема ни кого не заинтересовывает, то можно удалить ее...

Если кто хочет связаться то на depoint@mail.ru

← →
Iam (2008-02-13 12:09) [22]

de. (13.02.08 11:54) [21]
я уже давно не работаю с Delphi, мне просто любопытно было
500 рублей не плохо для такой пустяковой задачи, думаю с тобой свяжутся люди по e-mail

← →
Anatoly Podgoretsky © (2008-02-13 13:05) [23]

> de. (13.02.2008 11:26:11) [11]

По доллару за элемент множества, но деньги вперед.

← →
Anatoly Podgoretsky © (2008-02-13 13:06) [24]

> de. (13.02.2008 11:54:21) [21]

Тема заинтересовала, сумма нет.

← →
Johnmen © (2008-02-13 13:09) [25]

> думаю с тобой свяжутся люди по e-mail

Думаю к нему люди сразу домой придут.

← →
ShiZa (2008-02-13 15:34) [26]

См. почту

все алгоритмы существуют. вселенная бесконечно и в неопределенности континума сокрыто все потенциально возможное множество ответов.

А вообще сортируем циферки. (например 1 2 3 4 6 7 9 и сумма s=6)
быстро находим ближайшее меньшее искомой суммы, остальное отбрасываем
1 2 3 4 5

начиная справа

берем крайнее справа число (b=5)
двоичным поиском ищем второе слагаемое к нему (a), так чтобы b+a<=s
{при этом числа между a и p отбрасываются}
если a+b=s то первая комбинация найдена
если а+b<s то ищем третье слагаемое аналогично

Вообщем примерно так. Рекурсивно.

> vpbar © (13.02.08 16:00) [27]

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

интересно, доживу я до алгоритма создающего алгоритмы или нет...

> Palladin © (13.02.08 16:11) [29]
> интересно, доживу я до алгоритма создающего алгоритмы или нет...

Это-то не трудно само по себе, беда только в том, что задание такому алгоритму, котрый должен другие составлять - придется все едино человеку составлять :)

> Palladin © (13.02.08 16:11) [29]
> интересно, доживу я до алгоритма создающего алгоритмы или нет...

Так уже! Автошема подходит :)

> Это-то не трудно само по себе, беда только в том, что задание
> такому алгоритму, котрый должен другие составлять - придется
> все едино человеку составлять :)

Это только один раз. Попросить алгоритм создать алгоритм, который придумывает задания для алгоритма, который создает алгоритмы:)

> Palladin © (13.02.08 16:11) [29]
> интересно, доживу я до алгоритма создающего алгоритмы или нет...

Уже есть, разумеется, не всегда получается, и пока по соотношению время/качество_результата хуже, чем у двуногих.

> Уже есть, разумеется, не всегда получается

так значит все таки нет?

Afaik, люди в соседнем корпусе занимаются чем-то такого рода. Их программы генерируют исходный код и тестируют его по различным параметрам. Ну, и получается потом работающая программа. Разумеется, все это в стадии довольно сильно предварительных разработок (и сам я о них слышал краем уха), но программы работающие есть.

Разумеется, сегодня и, видимо, в даже не очень ближайшем будущем, проще, быстрее и дешевле нанять программиста.

> Их программы генерируют исходный код и тестируют его по
> различным параметрам

из каких соображений генерируют?
:)

Существуют ли алгоритмы ? Найти похожие ветки