Интересные интересности и задачи/головоломки

[Poma][a]

Poma][a, так а это... блин... у тя чё, нет более рационального решения?

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

[MihalNik]

Ну так дин. прог. - довольно очень простой по формулировке алгоритм:

Пусть d(i,c) максимальная сумма вплоть до c, для подмножества взятого из 1, ...,i элементов.
Заполним d(0,c) нулями.
Тогда меняя i от 1 до N, рассчитаем на каждом шаге d(i,c), для c от 0 до W, по рекуррентной формуле:
d(i - 1, c) для c = 0, ..., w_i - 1;
max(d(i - 1, c), d(i - 1, c - w_i) + w_i) для c = w_i, ..., W;
После выполнения в d(N,W) будет лежать максимальная сумма подмножества, не превышающая заданное значение.
Сложность алгоритма O(NW).

Но NP-сложный по времени.

[Smogg]

Где ошибка:

10001
+ 01001
+ 00101
-------------
11110

[pu4koff]

Эм... Нолик должен быть единичкой?)

[Smogg]

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

[ResourceSpace]

11103 ? %)

[Smogg]

как-то криво сформулировал задачу) это просто в троичной системе

[type_Oleg]

Чем особенна дата 3 ч 23 м 53 с , 2 января 1900 года ?
И 3 ч 23 м 54 с , 3 января 1900 года ?

[Вадим Мошев]

Ну, они обе имеют отрицательные значения в UNIX формате?

[type_Oleg]

Ну, у меня и дата рождения - тоже отрицательная в UNIX.