Представить суму всемя способами

← →
bogdan (2006-05-04 22:40) [0]

Привет мастера!
есть задачка:
задано неограниченное количество монет ЛЮБОГО номинала.
(например 2, 3, 7,15 или 1,4,7,25,50,70)
Задана сумма С.
нужно узнать сколько есть РАЗНЫХ способов представить суму С через заданые монеты
пример:
пусть номиналы: 2,3,5 а сумма 12.
тогда
12=2+2+2+2+2+2
=2+2+2+3+3
=3+3+3+3
=2+5+5
=5+3+2+2 тоесть 5 вариантов
Помогите плиз решить эту задачку..
Есть вариант перебрать все комбинации из номиналов
но если номиналов например 20, то перебирать нужно оч долго...
Заранее спасибо! Жду ответа.

← →
oldman © (2006-05-04 22:58) [1]

Пора открывать новый форум:
"Помогите написать курсовик тому, кто вместо учебы пиво пил!".

← →
Gero © (2006-05-04 23:03) [2]

Тебе нужно встретиться с Юликой. Я уверен, вместе вы что-нибудь придумаете.
А задачи — как нибудь потом...

← →
API © (2006-05-04 23:26) [3]

задано неограниченное количество монет ЛЮБОГО номинала
<...>
Помогите плиз решить эту задачку..

Для начала предоставьте неограниченное количество монет (можно не заморачиваться с монетами, а перейти стразу к купюрам, думаю, по 100$ будет самый раз) - а там уж мы и не такое решим! ;-)

← →
Труп Васи Доброго © (2006-05-04 23:29) [4]

bogdan (04.05.06 22:40)
Есть вариант перебрать все комбинации из номиналов
но если номиналов например 20, то перебирать нужно оч долго...
Да хоть 200 номиналов, хоть триста. С мощью современных процессоров это займёт не больше 1-2 минут, а это не долго.

← →
API © (2006-05-04 23:32) [5]

Да хоть 200 номиналов, хоть триста. С мощью современных процессоров это займёт не больше 1-2 минут, а это не долго.

Вот кабы банкоматы по 2 минуты деньги для выдачи считали... :-)

← →
McSimm © (2006-05-04 23:47) [6]

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

← →
Хозяин (2006-05-04 23:53) [7]

Что-то наподобие решал, только по подбору труб. Вспоминать неохота.

← →
Хозяин (2006-05-04 23:57) [8]

[7] + там не точно нужно было, какой-то зазор допускался.

← →
Yegorchic © (2006-05-04 23:58) [9]

> McSimm © (04.05.06 23:47) [6]

Решал такое в этом году на олимпиаде по информатике.

← →
Yegorchic © (2006-05-04 23:59) [10]

> Yegorchic © (04.05.06 23:58) [9]

Перечитал ещё раз [0] - решал чуть-чуть по легче. Совсем чуть-чуть...

← →
bogdan (2006-05-05 00:29) [11]

Впринципе ответов много но по сути ни одного, наверное вы все такие умные что даже идею не знаете.... А все решали... все знают....
Перебором НЕ ПОДХОДИТ, по-этому здесь и спросил !!!!!!!!!!!!

← →
Хозяин (2006-05-05 00:31) [12]

Подожди до утра, тут ведь дело такое, народ заинтерисовать нужно.

← →
bogdan (2006-05-05 00:32) [13]

>
> McSimm © (04.05.06 23:47) [6]
> А скажите, кому не жалко, только честно. Все ли из тех,
> кто отметился в ветке имеют представление о том, как это
> количество вариантов отыскивать?
> :))

Хоть кто то сообразил.... А не просто написал что попало...

← →
bogdan (2006-05-05 00:33) [14]

> Хозяин (05.05.06 00:31) [12]
> Подожди до утра, тут ведь дело такое, народ заинтерисовать
> нужно.

и чем.????????

← →
Хозяин (2006-05-05 00:35) [15]

bogdan (05.05.06 0:33) [14]
Кому интересно - тот и будет решать. Вроде так.

← →
DrPass © (2006-05-05 00:40) [16]

В случае произвольного набора номиналов эта задачка решается ТОЛЬКО перебором. Разве не так?

← →
API © (2006-05-05 00:46) [17]

[6] McSimm © (04.05.06 23:47)

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

← →
SergP © (2006-05-05 00:54) [18]

> bogdan (04.05.06 22:40)

Завтра пятница. Проси МВО чтобы он разместил задачу в завтрашнем выпуске пятничных задачек. Тогда будет большая вероятность что ее решат.

← →
Alx2 © (2006-05-05 02:27) [19]

Проста она слишком для пятницы.

{$APPTYPE CONSOLE} Type TIntegerArray = array of integer; procedure Solve(Const Nominals : TIntegerArray; Sum : Integer); Var sCount : Integer; Solution : TIntegerArray; procedure PrintSolution(idx : Integer); Var k : Integer; begin for k := Length(Nominals)-1 downto idx+1 do if Solution[k]<>0 then write(Nominals[k],"*",Solution[k]," "); writeln; end; procedure subSolve(idx,rest : Integer); Var newRest : Integer; Begin if rest = 0 then begin inc(sCount); printSolution(idx); end; if (idx>=0) and (rest>0) then begin newRest := rest; Solution[idx] := 0; while newRest>=0 do begin subSolve(idx-1,newRest); inc(Solution[idx]); dec(newRest,Nominals[idx]); end; end; End; Begin sCount := 0; SetLength(Solution,Length(Nominals)); subSolve(Length(Nominals)-1,Sum); Writeln("Count: ",sCount); End; Var Nominals : TIntegerArray; begin SetLength(Nominals,6); Nominals[0] := 2; Nominals[1] := 3; Nominals[2] := 5; Nominals[3] := 15; Nominals[4] := 23; Nominals[5] := 27; Solve(Nominals,100); end.

← →
bogdan (2006-05-05 02:55) [20]

> Проста она слишком для пятницы.

хоть она и проста, но СПАсибо

> Alx2 ©

ПОПРОбую разобраться.....
Большой сенкс....

← →
Хозяин (2006-05-05 05:21) [21]

Alx2 © (05.05.06 2:27) [19]

Немогу найти, например, вот это:
15*6 3*2 2*2

Ведь на примере(у автора) показано, что необязательно использовать все номиналы.

← →
Alx2 © (2006-05-05 09:12) [22]

>Хозяин (05.05.06 05:21) [21]

???
Не понял вопроса. В приведенном примере оно (15*6 3*2 2*2
) идет 524 строкой.

← →
Хозяин (2006-05-05 09:15) [23]

А у меня все начинаются на 27 :(

Сейчас посчитаю строки, а итог 1368 (D6)

← →
Хозяин (2006-05-05 09:19) [24]

не может быть 1368, это у меня консольное окно обрезало :)

начало
27*1 15*1 5*4 3*12 2*1
конец
27*3 15*1 2*2

Извени
:)

← →
Alx2 © (2006-05-05 09:20) [25]

>Хозяин (05.05.06 09:19) [24]
Так запускать лучше: file.exe > lst.txt
А потом смотреть lsts.txt :)

← →
Хозяин (2006-05-05 09:22) [26]

Ну а я из Делпхи, только поставил readln; :)

← →
Rulikkk (2006-05-05 11:10) [27]

Господа, а Вам часом не кажется, что это задачка на динамическое программирование? То есть например надо предстваить 100, имея 5, 7, 2 (например).
Заводим массив - от 1 до 100. На самом деле реально хватит хранить только 7 или 8 его последних элементов (т.к. максимальный номинал - 7).
В нём будем хранить кол-во вариантов представления для номера элемента. То есть в первом элементе - 0, т.к 1 никак не получишь. Во втором - 1, т.к. только одним способом можно представить.
Изначально он будет заполнен нулями. Заполняя i-ый элемент мы будем смотреть, есть ли не нули в элементах (i-5), (i-7), (i-2) и суммировать все эти значения. И так далее, до 100.

← →
bogdan (2006-05-05 15:52) [28]

> [27]

А например, а то динамическое программирование для меня оч слабовато,
..............

Я вот еще не могу понять до конца как работает [19]

тяжело доходит, а еще на delphi "переносить"....

← →
Alx2 © (2006-05-05 16:17) [29]

>bogdan (05.05.06 15:52) [28]

Оно уже на Delphi. Куда еще переносить? Заменить или выкинуть вывод через writeln - весь перенос.

>Я вот еще не могу понять до конца как работает [19]

Рекурсия. Есть набор монет и есть сумма. Если мы возьмем одну монету из набора, то сумма уменьшится. Получили снова такую же задачу, с тем же набором монет, но новой суммой. Значит, действуем точно так-же. Как только от новой суммы остался "0" - значит, разменяли все.

← →
TUser © (2006-05-05 16:25) [30]

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

Мысль состоит в том, чтобы получить решение не одной, а множества возможных задач. Применительно к здесь - найти число способов, которыми можно выразить сумму 1, сумму2, 3, 4, ..., 100. Допустим значения для сумм 1..N известны. Тогда легко найдем значения для N+1. Например, если у нас есть монеты достоинства 2 и 3, то число таких способов есть С[N-1] + С[N-2]. Так потихоньку до сотни доберешься.

← →
Alx2 © (2006-05-05 16:30) [31]

>Не надо использовать рекурсию, там где можно обойтись ДП.

Закон, и номер статьи, пожалуйста :)

Понеслось. Числа Каталана, комбинаторные порождающие функции, интегрирование в комплексной плоскости вокруг полюса. :) Из пушек по воробьям.

← →
TUser © (2006-05-05 17:09) [32]

> Alx2 © (05.05.06 16:30) [31]

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

← →
Alx2 © (2006-05-05 19:19) [33]

>TUser © (05.05.06 17:09) [32]

Сижу, глотаю сопли... Уел, блин, отповедью :)

Извини, что привел переборный и к тому же рекурсивный алгоритм и покоробил чувство прекрасного. :) Впредь всегда буду стремиться в ДП к отсутствию рекурсии, а в алгоритмах - к минимальной сложности. :)

"Не надо использовать рекурсию, там где можно обойтись ДП" - теперь моя максима.

← →
TUser © (2006-05-05 19:30) [34]

Зря ты ерничаешь.

← →
Alx2 © (2006-05-05 19:39) [35]

>TUser © (05.05.06 19:30) [34]

На самом деле вопрос серьезный. Не будем лезть в философию где использовать рекурсию, а где - нет. И будем тратить усилия на поиска оптимума по сложности, тогда, когда он нужен.

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

← →
Alx2 © (2006-05-05 19:46) [36]

Я через рекуррентное соотношение, следуещее из той самой рекурсии, получил нечто подобное.

← →
MBo © (2006-05-05 19:48) [37]

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

← →
Alx2 © (2006-05-05 19:51) [38]

>MBo © (05.05.06 19:48) [37]

>а тут нужно выдать все решения

Теперь только количество.

[37] continued...
c, похоже, меньшими затратами памяти - стек глубиной в VerySmallConst*Sum/MinValue против весьма солидного дерева у ДП (тут могут быть варианты, возможно, я преувеличиваю)

>Alx2 © (05.05.06 19:51) [38]
>Теперь только количество"

Пардон, не обратил внимания. Тогда ДП значительно упрощается по сравнению с тем вариантом, о котором я думал.

У ДП и память линейная и никакого дерева. Сейчас напишу.

>TUser © (05.05.06 19:58) [41]
>У ДП и память линейная и никакого дерева
Я, к сожалению, рассуждал о subj "Представить суму всемя способами" без уточнения, что нужно только число способов ;)

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

Сложность O(NM), O(N) памяти, где N - сумма, M - мощность набора

function CalcVarCount(const Data: array of Integer; Sum: Integer): Integer; var X, i, j: Integer; A: array of Integer; begin SetLength(A, Sum + 1); for i := 0 to High(Data) do begin X := Data[i]; if X > Sum then Break; Inc(A[X]); for j := Data[0] to Sum - X do Inc(A[j + X], A[j]); end; Result := A[Sum] end;

>А можно поподробнее???
Что именно непонятно?

[44]
как работает алгоритм... вернее что он делает? почему от 0 до sum-xкакой смысл в этом? Inc(A[j + X], A[j]);

Попробуй на бумаге разобраться - возьми набор монет 2,3,5 (Data) и выпиши в ряд числа от 2 до 12-15 (массив A), а далее пошагово проходи по алгоритму, ставя против соотв. сумм точки в количестве, на которое Inc увеличивает

я попробую но вот это для меня пока что недосягаемо....
Inc(A[j + X], A[j]);

> недосягаемо.... Inc(A[j + X], A[j]);
Ну уж справку по Inc бы посмотрел. Это аналог
A[j + X] := A[j + X] + A[j];

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

почему на единицу прибавляем? Inc(A[X]);

>Обьясните, пожалуйста, каково предназначение массива А?
Для реализации принципа динамического программирования.
Мы решаем сначала маленькие подзадачки, записывая результат в массив, а потом используем эти результаты при решении более крупных задач, которые включают в себя маленькие.
Из монет в 2 копейки мы можем составить суммы 2,4,6,8... - ставим единички в массиве А
Затем решаем для 3 копеек - ставим единичку в A[3], потом проходим со второго элемента по j, увеличивая j+3 элементы. При этом 9 элемент увеличиваем на 2, поскольку в 6 уже записано 2 способа (2+2+2 и 3+3) и так далее...

пасибо... думаю что смогу осилить... РЕСПЕКТ

Представить суму всемя способами Найти похожие ветки