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

← →
MBo © (2006-05-05 19:57) [40]

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

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

← →
TUser © (2006-05-05 19:58) [41]

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

← →
MBo © (2006-05-05 20:03) [42]

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

← →
TUser © (2006-05-05 21:12) [43]

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

← →
MBo © (2006-05-06 01:49) [44]

Сложность 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;

← →
snikers © (2006-05-10 16:20) [45]

> MBo © (06.05.06 01:49) [44]

Inc(A[X]); for j := Data[0] to Sum - X do Inc(A[j + X], A[j]);
А можно поподробнее???

← →
MBo © (2006-05-10 16:29) [46]

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

← →
snikers © (2006-05-10 17:44) [47]

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

← →
MBo © (2006-05-10 17:59) [48]

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

← →
oldman © (2006-05-10 18:10) [49]

> MBo © (10.05.06 17:59) [48]
> Попробуй на бумаге разобраться - возьми набор монет 2,3,
> 5

нет уже таких монет :(((

← →
snikers © (2006-05-10 18:15) [50]

я попробую но вот это для меня пока что недосягаемо....
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) и так далее...

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

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