Алгоритмы

[Cris]

Люди хто что подскажит в инете статейку какуенить про динамическое программирование,
меня собственно интересует алгоритмы такиех задач как:
о рюкзаке(но некакойто галимый жадный алгоритм) - с тем что можно юзать несколько раз 1 предмет, или бесконечно
про ежиков(мышей, принца) - пройти с одного угла в другой оп прямоугольнику разделенного квадратиками, так чтоб собрать наибольше количество чево-либо что на них лежит, при том что двигаться можно только в низ или вправо(относительно если начинать сверху)
про банкомат - есть сума S, и набок купюр - a1,a2,a3...an, нужно найти минимально количество купюр из которой омжно составить данную суму:
S=8
a1=6
a2=1
a3=1
a4=4
a5=4
ответ: 4+4=8 - т.е 2
а если делать жадным то получаеться 6+1+1=8 т.е 3((
algolist i Wiki не предлагать)

 

[PainKiller]

Ы. Кто-то решил делать игрушку?)

 

[Cris]

Ы. Кто-то решил делать игрушку?)

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

 

[dreamer]

про банкомат - есть сума S, и набок купюр - a1,a2,a3...an, нужно найти минимально количество купюр из которой омжно составить данную суму

Мог бы и поискать в инете
Но попытаюсь объяснить:
это называется "динамическое программирование". На примере с купюрами:
Попробуем определить необходиму функцию рекурсивно:

coins = [1,2,5,10,25,50,100]
 -- количество монет для размена суммы
define amount(sum):
  if (sum <= 0): resut is NONE,
  else if (sum in coins): result is 1,
  else result is minimum of { amount (sum - coin) + 1 } for all coin in coins.

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

 

[Cris]

Мог бы и поискать в инете
Но попытаюсь объяснить:
это называется "динамическое программирование". На примере с купюрами:
Попробуем определить необходиму функцию рекурсивно:

coins = [1,2,5,10,25,50,100]
 -- количество монет для размена суммы
define amount(sum):
  if (sum <= 0): resut is NONE,
  else if (sum in coins): result is 1,
  else result is minimum of { amount (sum - coin) + 1 } for all coin in coins.

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

ну попробую))

 

[Cris]

Терь мне нужно придумать динамику к такой задаче(я знаю что класика но мн их нехто необьяснял)
есть N чисел вес камней
нужно разложить их все так чтобы разница между обшими весами двух куч была минимальная:
10 8 8 4 10
ответ 0, так как первая куча: 10+10=20, вторая 8+8+4=20

 

[Cris]

такс, есть задачка по иеории игр:
есть N кучек камней, за одих ход разрешаеться или забрать лубое количество камней с однйо кучи(в том числе и всю кучу) или разделить одну кучу на две по меньше(1+3=4, 2+2=4 ....) выигрывает тот хто возьмет последний камушек

В первой строке задано количество тестовых случаев T (1 <= T <= 100) Далее следует T пар строк, в первой из которых находится значение N, а во второй через пробел количества камушков в каждой из кучек Si.
1 <= N <= 10^3
1 <= Si <= 10^6

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

 

[Cris]

впринципе уже помощь не требуеться, уже нашол человека который мне помог: эта игра наз. Ним, и решаеться по теореме Спрага-Грюнди(Шпрага-Грюнди, -Гринди, - Гранди)

 

[Cris]

МОжет хто знает:
нужно модифицировать алгоритм построения выпуклой оболочки, обычно он строиться для множества точек, в моем случае мне нужно построить такую оболочку для окружностей, которые могут пересекаться. тоесть есть множество окружностей (x,y,r) надо вокруг них натянуть веревочку минимальной длинны, окружности пересекаються и имеют разные радиус,
была идея: до нужной точности разбить все окружности на набор точек, но получаеться много точек, и время будет тянуть долго

 

[dreamer]

МОжет хто знает:
нужно модифицировать алгоритм построения выпуклой оболочки, обычно он строиться для множества точек, в моем случае мне нужно построить такую оболочку для окружностей, которые могут пересекаться. тоесть есть множество окружностей (x,y,r) надо вокруг них натянуть веревочку минимальной длинны, окружности пересекаються и имеют разные радиус,
была идея: до нужной точности разбить все окружности на набор точек, но получаеться много точек, и время будет тянуть долго

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