Сумма неизвестных слагаемых

[tardis]

Сумма неизвестных слагаемых

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

 

[zerkms]

зачем рекурсия?
отсортируй и подбирай. причём подбор получится вполне осмысленный, а не тупой перебор

 

[dimagolov]

Задача непонятна. так как наверняка можно найти более одного такого набора, то искать надо или все возможные или оптимальный по какому-то критерию.
Если первое, то понятно, что из N чисел есть комбинаторное кол-во выборок по M неповторяющехся значений, причем M у нас будут от 1 до N включительно. Это будет общее кол-во вариантов, которые надо проверять. Еще можно (с обратной стороны) бить отрезок (сумму) на части, понятно, что их кол-во будет меньше или равно длинне отрезка (если ограничиваемся натуральными числами), число возможных разбиений (теперь уже всех возможных) тут будет тоже кол-во выборок из S по M, M=1..S. Останется отобрать такие выборки, которые удовлетворяют начальному набору чисел.

Ну а если вопрос об неком оптимальном варианте, то вопрос каков этот критерий

 

[tardis]

ну отсортирую я к примеру к такой последовательности
1,2,3,4,5,6,7
а сумма пусть будет 2+4+5 = 11
как тут без рекурсии подобрать слагаемые 2,4,5 ?

-~{}~ 07.10.08 15:05:

Ну а если вопрос об неком оптимальном варианте, то вопрос каков этот критерий

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

а вот алгоритм надо такой, чтоб при кол-ве слагаемых около 50, скрипт не уходил в нирвану

-~{}~ 07.10.08 15:10:

числа не только натуральные, да и как тут можно разбить не совсем понимаю

 

[zerkms]

ах, да, пардон, с рекурсией проще

 

[tardis]

это сарказм или я сегодня переработал?

 

[zerkms]

не сарказм интересная задачка
счас попробую написать что-нить вменяемое

 

[tardis]

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

чаще всего возможных слагаемых не больше 20-25, а сегодня попалось 48

-~{}~ 07.10.08 15:36:

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

но на будущее все равно хочется узнать, можно ли сделать быстрее и проще

 

[zerkms]

не выкладывай его пока, думаю что не один человек сейчас сидит и пишет свою реализацию ))

 

[AmdY]

в уме считать такое анреал.
а атоматизировать такое интересно, но ну его нафег, а то работа на пару часов уйдёт на второй план

 

[zerkms]

Ну вроде тоже реализовал приведи примерные "большие" наборы тестовых данных

-~{}~ 07.10.08 23:01:

Spoiler: http://pastebin.ru/297413

 

[tardis]

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

 

[whirlwind]

Предлагаю устоить соревнование на самый быстрый алгоритм. Вместе с вариантами выкладывайте замеры времени, а ТС пусть выложит набор входных данных.

 

[tardis]

держите

$summands = array ( 0 => 413.28, 1 => 1662.96, 2 => 1566.53, 3 => 1238.86, 4 => 10676.4, 5 => 7812.96,  
6 => 2420.64, 7 => 1426.8, 8 => 34302.24, 9 => 846.24, 10 => 541.2, 11 => 747.84, 12 => 1492.73, 13 => 413.28,  
14 => 2490.5, 15 => 5697.36, 16 => 2046.72, 17 => 2332.08, 18 => 3168.48, 19 => 1820.4, 20 => 2538.72, 21 => 21976.66,  
22 => 966.29, 23 => 639.6, 24 => 12290.16, 25 => 1202.45, 26 => 18710.76, 27 => 9613.68, 28 => 2607.6, 29 => 606.14,  
30 => 6386.16, 31 => 4910.16, 32 => 113.16, 33 => 3949.78, 34 => 2942.16, 35 => 1398.27, 36 => 1426.8, 37 => 211.56,  
38 => 68.88, 39 => 7901.52, 40 => 678.96, 41 => 2084.11, 42 => 32629.44, 43 => 1170.96, 44 => 21638.16, 45 => 2169.72,  
46 => 1062.72, 47 => 1230,  
) ; 
   
$sum = 130445.93;

 

[zerkms]

хехе в 300секунд не уложился %)

 

[kabachok]

предлагаю не выкладывать свои варианты до опр. времени, самому интересно поучавствовать, но смогу только после работы.

давайте выложим варианты после 0.00 по Москве

 

[tardis]

хехе в 300секунд не уложился %)

чудес я и не ждал

предлагаю не выкладывать свои варианты до опр. времени

почему бы не выкладывать на pastebin, кто не хочет - смотреть не будет

 

[berkut]

тогда уж учавствующие скиньтесь на приз победителю)

 

[AmdY]

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

 

[kabachok]

Вопрос, массив на выходе должен сохранять ключи? заданные в начале?