Если я использую динамическое программирование для размена монет, какой будет матрица для запоминания?

Я не понимаю, как должна выглядеть матрица для метода динамического программирования проблемы с монетами. Скажем, у меня есть номиналы 1c, 5c, 10c и 25c, и я вызываю внесение изменений (10). т. е. я хочу внести сдачу на 10 центов, как должна выглядеть моя окончательная матрица/массив. Мне нужно это знать, так как я хочу назначить массив в начале программы. Я не ищу код здесь.


algorithm dynamic-programming coin-change
person Phoenix    schedule 02.10.2012    source источник
comment
Что именно вы хотите найти? Сколько разных способов получить сумму 10?   -  person Ivan Vergiliev    schedule 03.10.2012
comment
Да, это правильно. Количество способов получить сумму до 10   -  person Phoenix    schedule 03.10.2012

Ответы (2)


arrow_upward
2
arrow_downward

Вы можете использовать матрицу, в которой одно измерение показывает сумму, для которой вы рассчитываете прямо сейчас, а другое показывает, какие монеты вы можете использовать — например, первая строка показывает количество способов достичь заданной суммы, используя только монеты 1c. , второй ряд - 1с и 5с, третий - 1с, 5с и 10с и так далее.

Итак, в вашем примере это может выглядеть так:

Sum:  0 1 2 3 4 5 6 7 8 9 10
Ways: 1 1 1 1 1 1 1 1 1 1 1   (using only 1c coins - N x 1c)
      1 1 1 1 1 2 2 2 2 2 3   (using 1c and 5c coins - either Nx1c, 1x5c + (N - 5)*1c or 2x5c)
      1 1 1 1 1 2 2 2 2 2 4   (using 1c, 5c and 10c coins - one of the above, or 1x10c)

Однако вам не нужно хранить всю матрицу - последней строки всегда должно быть достаточно.

Объяснение того, как избавиться от большей части матрицы:

Предположим, вы нашли ответ, используя только монеты 1c (что не так уж сложно сделать), и он хранится в одном массиве, скажем, DP. Теперь у вас есть эта информация, и вы хотите знать ответ для монет 1c и 5c.

Можно исходить из sum = 0 to 10, сохраняя следующий инвариант:

  • когда вы вычисляете ответ для sum, запись в DP для каждого числа x между 0 и sum - 1 включительно показывает количество способов получить sum, используя монеты 1c и 5c. Все остальные записи (от sum до конца массива) содержат ответ только при использовании монет 1c.

И поддерживать его на самом деле довольно просто: когда вы вычисляете ответ для x, вы знаете:

  • количество способов получить x используя только монеты 1c - это DP[x], так как мы его еще не перезаписали;
  • количество способов получить x, используя хотя бы одну монету 5c - это DP[x - 5], т.е. количество способов получить то количество монет, которое останется после того, как мы удалим 5c (или 0, если x - 5 < 0).

Затем вы можете просто суммировать эти два числа и сохранить результат в DP[x]. Затем аналогично продолжайте для остальных монет.

person Ivan Vergiliev    schedule 02.10.2012
comment
почему мне не нужно хранить всю матрицу? почему последней строки достаточно? Можете ли вы привести пример с 10 центами, как будет достаточно последней строки. - person Phoenix; 03.10.2012
comment
Смотрите отредактированный ответ - он получился немного длинным, но я надеюсь, что он понятен. - person Ivan Vergiliev; 03.10.2012
comment
Привет Иван. можете ли вы показать, как здесь будет рассчитываться dp[10], а не только для x. как dp[10] окажется равным 4 - person Phoenix; 03.10.2012
comment
Попробуйте смоделировать алгоритм, который я описал, вручную — это поможет вам лучше понять его. Сделайте это сначала для некоторого меньшего числа, может быть, даже с более мелкими монетами (например, 1c, 2c, 5c). Тогда вы можете сообщить мне, если у вас есть какие-либо проблемы. - person Ivan Vergiliev; 03.10.2012
comment
Если вы еще не поняли - количество способов получить 10, используя монеты 1c, 5c и 10c - давайте назовем это способами (10, 3) - сначала сумма, затем количество различных монет, которые мы используем - это: способы (10, 3) = способы (10 - 10, 3) + способы (10, 2) - первый - взять одну монету 10 центов, сколькими способами можно получить то, что осталось, второй - число способов получить 10, используя только монеты 1c и 5c. пути (0, 3) = 1, пути (10, 2) = 3 по аналогичной логике. - person Ivan Vergiliev; 07.10.2012

arrow_upward
0
arrow_downward

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

{0 => (),
 1 => (1),
 2 => (1,1),
 3 => (1,1,1),
 ...
 13 => (10,1,1,1)
 ...
}
person ajon    schedule 02.10.2012