монета -разменная монета

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

Вход:

• сумма xмы хотим заплатить монетами за некоторую стоимость.
• набор d, представляющий количество доступных монет достоинством (1c, 5c, 10c, 25c, 100c, 200c)

Выход:

• Минимальное количество монет, которые необходимо разменять руками для выплаты.

Предположения:

• Кассовый оператор имеет неограниченный запас монет и знает, как выдать оптимальную сдачу.

Что я пытался сделать до сих пор:

Я пытаюсь построить массив C, так что каждый элемент C[i] представляет собой /минимальное/количество монет, которые обмениваются руками на сумму i.

С[0] = 0

Для C[i] я вычисляю его, либо беря минимум всех C[i -di] плюс 1 для всех доступных номиналов монет. Затем я удаляю монету, которую я выбрал из доступных монет.

Этот подход работает в простых случаях, но когда у меня, например,:

99 99 0 0 0 1 0

Мой подход терпит неудачу,потому что «дешевле» сделать 1 доллар, который даст обмен 2 монет, чем заплатить точные 99 центов в центах (при обмене 99 монет ).

Любые указатели будут оценены.