Изменение монеты - максимальное количество поиска

Question

Мне сложно понять, как объяснить эту проблему. В настоящее время я пытаюсь создать программу для дополнительного кредита в своем классе программирования, но я даже не понимаю математику за ней ... Поэтому я бы очень хотел, чтобы кто-то мог мне помочь. Хорошо:

Скажите, что у вас есть монета в 1 цент и монета в 4 цента. И общее количество разрешенных монет равно 4. Максимальное покрытие составляет 11. График ниже.

Value | 1 cent | 4 cent 
1 | 1 
2 | 2 
3 | 3 
4 | 4 
5 | 1  | 1 
6 | 2  | 1 
7 | 3  | 1 
8 |  | 2 
9 | 1  | 2 
10 | 2  | 2 
11 | Maximum 

S0 это пример. Мне нужно сделать это для чего-то большего. Но я хотел бы, чтобы кто-то помог мне объяснить математику. Или что такое уравнение ... Это сводит меня с ума.

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

EDIT: изменен на 11

Answer 1

динамического программирования (ДП) является способом решить эту проблему. DP обычно включает в себя поиск некоторого базового свойства, которое вы можете вычислить на основе других значений этого свойства - формы индуктивных рассуждений.

В вашем случае основной вопрос, который вам нужно задать, заключается в следующем: «Могу ли я сделать n центов, используя ровно k монет». Это просто boolean yes/no; потому что вы можете повторно использовать монеты, вам не нужно знать , как сделать n центов с k монетами, только ли это возможно. Это неявно определяет булевую матрицу A[n][k], где A[n][k] = TRUE, если вы можете сделать n центов с k данных видов монет.

Изучите отношения между различными элементами этой таблицы истинности. Например, если я могу сделать 5 центов с 2 монетами, то это означает, что я могу сделать 6 и 9 центов каждый с 3 монетами (почему?); таким образом, A[5][2] подразумевает A[6][3] и A[9][3].

Удачи вам!

Answer 2

Примечание: я переписываю сообщение, потому что другой ответ был удален во время обновления, чтобы обеспечить больше контекста.

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

Однако, вот краткое изложение того, как работает этот алгоритм, с помощью динамического программирования:

Предположения:
Каждое значение в T ограничивается Integer.MAX_VALUE
T является сдерживаются Integer.MAX_VALUE -1

Определения :
D = {d1, d2, ..., dk}∀ d∈ℤ, ∀ w_d = 1
T = W = Total Weight of Knapsack = Total Coins Available for Use

Как работает алгоритм:

1. Обеспечивает W > 0 и что 1 ∈ D
2. Гарантирует ограничения выше выполнены
3. Создать массив динамически размера MinCoins[0] = 0
4. Пусть n=1 и итерацию по 1 как n→∞
   • Для каждой итерации, установите MinCoins[ n ] = Integer.MAX_VALUE
   • итерацию по каждому элементу в D, пусть каждое значение будет называться d во время итерации
     • Если d > n пропустить этот итерационный
     • Пусть z представляют оптимальное количество монеты для этой итерации
     • Получите оптимальное количество монет из предыдущей итерации и добавьте еще одно (от этого значения) к нему: z = MinCoins [ n - d ] + 1
     • Теперь сравните z к MinCoins[ n ]
     • Если z < MinCoins[ n ] новое оптимальное решение было найдено (сохранить), иначе итерации к следующему d
   • Пусть оптимальное решение, найденное для этой итерации определяется как q = MinCoins[ n ]
   • Если q < T, перейдите к следующей итерации. Иначе, никакое максимальное решение не было найдено этой итерацией и нарушить цикл.

https://bitbucket.org/asraful/coin-change