Блог пользователя dudeboy

Помогите решить задачу на ДП
Автор dudeboy, 13 лет назад, По-русски

Вот уже 4 дня не могу решить задачу - http://acmp.ru/index.asp?main=task&id_task=407

Как будет выглядеть таблица динамики ?
Помогите пожалуйста с разбором.
  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Рюкзак,разрешение повторов достигается проходом в прямом порядке(по массиву, а не таблице), а не в обратном.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Думаю здесь можно написать простую динамику. z[i] - наименьшее количество монет которым мы можем набрать сумму i. Изначально все z[i] = INF, кроме z[0] = 0. Ну и теперь перебираем какую монету возьмём и делаем переход вперёд. Решение за O(N * K)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не могу понять, приведите пример таблицы динамики Z приминительно к тесту :
    N = 3
    arr = 1 5 7
    sum = 19
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Знаешь смотреть на таблицу динамики (в данном случае массив) не самый лучший способ разобраться с обычной динамикой. Её нужно понимать, а смотреть на массив бестолку
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Динамика должна подразумевать рекурентную формулу, я не могу в этой задаче увидеть её, к сожалению :(
        Какая зависимость между предыдущим и  последущим элементом массива Z будет ?
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Вы сами можете написать это и посмотреть на массив
          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          F(S) = сколько нужно монет что б набрать сумму S

          F(S) = MIN ( F(S-a1) , F(S-a2), .... F(S-an) ) + 1

          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Т.е. ограниченным - например 5 монет достоинством в 10 руб., 4 монеты по 50 руб и т.д.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тогда делаем кучу одинаковых монет и не разрешаем брать одну и ту же дважды
    Решение за (общее кол-вомонет*К)
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не могу понять, приведите пример таблицы динамики Z приминительно к тесту :
N = 3
arr = 1 5 7
sum = 19
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    0 - 0

    1 - 1

    2 - 2

    3 - 3

    4 - 4

    5 - 1

    6 - 2

    7 - 1

    8 - 2

    9 - 3

    10 - 2

    11 - 3

    12 - 2

    13 - 3

    14 - 2

    15 - 3

    16 - 4

    17 - 3

    18 - 4

    19 - 3

    Вот таблица, хоть я и мало верю, что она сильно поможет Вам в понимании ДП.

    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://informatics.mccme.ru/moodle/mod/book/view.php?id=815 (может поможет разобраться)
→ Ответить