Проблема размена монет — это классическая задача динамического программирования, вариантом которой является минимальная сдача монеты.Эта статья будет ссылаться на предыдущую статью 01 Идеи решения проблем с рюкзаком, чтобы подробно объяснить проблему минимальной сдачи монет. Если вам нужно просмотреть предыдущую статью, вы можете нажать на ссылку ниже:Подробное объяснение задачи динамического программирования 01 о рюкзаке — реализация JavaScript
Вы также можете просмотреть следующую статьюПодробное объяснение самой длинной общей последовательности динамического программирования — реализация JavaScript.
Давайте начнем.
вопрос
Учитывая 4 номинала монет в 1 цент, 2 цента, 5 центов и 6 центов, если вы ищете 11 центов сдачи, что вы можете сделать, чтобы минимизировать сумму монет, которые вы ищете?
анализировать
Проблема минимальной сдачи монет состоит в том, чтобы найти комбинацию монет, поэтому основная предпосылка состоит в том, что существует неограниченный запас монет. Создадим следующую таблицу для анализа проблемы:
где j представляет общую сумму сдачи в каждом столбце, а каждая строка i представляет номинал монеты.T[i][j]Указывает количество монет, которое мы собираемся заполнить в форме.
Перед заполнением формы нам необходимо уточнить несколько правил:
- При заполнении строки i используйте только монеты номиналом i и меньше. Например, если я заполняю строку 0, i=0, то можно использовать только монеты номиналом 1 цент. Когда я заполняю строку 2, i=2, то можно использовать монеты трех номиналов: 1 цент, 2 цента и 5 центов.
- При заполнении j-го столбца указывается общая сумма, которую в данный момент необходимо восполнить монетами. Например, j=6, что означает, что вам нужно использовать монеты, чтобы получить в общей сложности 6 очков.
1. i = 0
Когда мы можем использовать только монеты достоинством в 1 цент, согласно вышеизложенным правилам, то понятно, что для суммы в несколько центов нужно несколько монет. которыйT[i][j] = j.
2. i = 1
Когда у нас есть два номинала в 1 цент и 2 цента, то комбинация относительно больше.
i=1 j = 1: когда общая сумма равна 1, можно использовать номинал только в 1 цент. То есть заполнить 1.i=1 j = 2: Когда сумма равна 2, вы можете использовать 2 1-очковых или 1 2-очковых. Поскольку нам требуется минимальное количество монет, используйте 1 2 цента. В таблице указано количество монет, поэтому здесь также укажите 1.i=1 j = 3: Когда сумма равна 3, вы можете использовать 3 1 очко или вы можете использовать 1 1 очко плюс 1 2 очка. Поэтому здесь следует заполнить 2.i=1 j = 4: когда общее количество равно 4, вы можете использовать 4 1-очка, 2 1-очко плюс 1 2-очко или 2 2-очка. Дело с наименьшим количеством монет должно быть 2 2 цента. Так что заполните 2 здесь.i=1 j = 5: когда сумма равна 5, комбинаций больше, но вы должны подумать об использовании 2 2s и 1 1 для достижения минимального требования к монетам. Так что заполните 3 здесь.
Давайте посмотрим на ситуацию после заполнения вышеуказанных 5 коробок:
Предлагаю вам сделать стол по моему рисунку на бумаге самостоятельно. Далее не торопитесь заполнять форму. На основании имеющихся данных сделаем вывод, чтоT[i][j], затем подтвердите, заполнив оставшиеся формы.
Мы используем массив монеты [i] для представления номинала монеты, согласно таблице 1 балл = монеты [0], 2 балла = монеты [1].
Когда jT[i][j] == T[i-1][j]. Как мы видим из таблицы,T[1][1]==T[0][1].
Когда j>=coins[i], в соответствии с существующей строкой i=1 можно вывести правило, пустьa = 1+T[i][j-coins[i]],T[i][j]= min(T[i-1][j],a), то есть минимальное значение получается путем сравнения двух. Может быть, сначала вы видите эту формулу об a, и она слишком внезапна, чтобы ее принять. Чтобы немного пояснить, в i-м ряду предпочтительно выбирается одна и та же монета, потому что монета в этом ряду имеет самый большой номинал и, скорее всего, сделает общее количество монет наименьшим. следовательноj-coins[i], легко понять, то есть после выбора монет в этом ряду, сколько всего осталось. Например, когда i=1, j=3, j-coins[1]=1. Затем, после выбора 2 точек, оставшаяся сумма равна 1. В это время мы находим i=1, j=1, то есть T[1][1], его значение равно 1 плюс константа 1, то есть Окончательный результат 2.
Другой пример:i=1 j=5. Поскольку форма заполняется слева направо, заполняются все формы с i=1 и jT[1][3]=2, добавьте константу 1, чтобы получить окончательный результатT[1][5]=3.
На самом деле, сама формула очень короткая и легко запоминается. Если вы действительно не можете этого понять, не беспокойтесь об этом. Сначала сверните браузер, не читайте оставшуюся часть этой статьи. С помощью этой формулы решения проблем вы можете заполнить форму полностью на бумаге, и вы можете медленно понимать ее в процессе заполнения формы и ее анализа.
3. Оставшееся содержимое
Согласно формуле, представленной на предыдущем шаге, фактически всеT[i][j]можно заполнить. форму ниже.
Рекомендуется сначала заполнить форму на бумаге, а потом сравнить ее с моей картинкой, чтобы увидеть, нет ли расхождения в ответе.
4. Псевдокод
Приведенная выше логика заполнения формы выражается псевдокодом следующим образом
if(i == 0){
T[i][j] = j/coins[i]; //硬币找零一定要有个 最小面额1，否则会无解
}else{
if(j >= coins[i]){
T[i][j] = min(T[i-1][j],1+T[i][j-coins[i]])
}else{
T[i][j] = T[i-1][j];
}
}
5. Найдите комбинации
На этом мы почти закончили заполнение формы. Следующее, что нужно искать, это найти комбинации монет из таблицы. 🤔
Вопреки порядку заполнения формы поиск комбинаций начинается с нижнего угла.
Первое, что должно быть ясно, это то, что еслиT[i][j] == T[i-1][j], затем выполните поиск вверх. Проанализируйте по рисунку:
1.ТаргетингT[3][11], так как нетT[i][j] == T[i-1][j], поэтому вам не нужно искать вверх, обязательно выберите один6分монета.Идея поиска комбинаций и заполнения T[i][j] почти обратная.
2.После выбора монеты в 6 центов остается 11-6=5. Следовательно, он расположен в T[3][5]. Поскольку T[3][5]==T[2][5], посмотрите на синюю стрелку на рисунке и выполните поиск вверх, покаT[i][j] != T[i-1].
3.Он находится в T[2][5], а монеты[i] в это время равны 5 очкам. Выбираются только 5-центовые монеты, а оставшаяся сумма равна 5-5=0.
4.Когда j=0, поиск заканчивается. Выбранная комбинация монет, определяемая вышеуказанными шагами, составляет: 1 5 очков, 1 6 очков.
код
Вышеизложенное является идеей анализа всей проблемы минимальной раздачи монет. Окончательный код реализован на JavaScript.Если ваш Sublime поддерживает чистый JavaScript, вы можете напрямую скопировать и вставить код, выполнить команду + b напрямую, чтобы просмотреть результаты, а затем изменить входные переменные, чтобы просмотреть выходные результаты в большем количестве случаев.
//动态规划 -- 硬币找零问题
function minCoins(coins,total,n){
var T = [];
for(let i = 0;i<n;i++){
T[i] = []
for (let j=0;j<= total;j++){
if(j == 0){
T[i][j] = 0;
continue;
}
if(i == 0){
T[i][j] = j/coins[i]; //硬币找零一定要有个 最小面额1，否则会无解
}else{
if(j >= coins[i]){
T[i][j] = Math.min(T[i-1][j],1+T[i][j-coins[i]])
}else{
T[i][j] = T[i-1][j];
}
}
}
}
findValue(coins,total,n,T);
return T;
}
function findValue(coins,total,n,T){
var i = n-1, j = total;
while(i>0 && j >0){
if(T[i][j]!=T[i-1][j]){
//锁定位置,确定i,j值，开始找构成结果的硬币组合。 其实根据这种计算方法，只需要考虑最右边那一列，从下往上推。
//console.log(T[i][j]);
break
}else{
i--;
}
}
var s = []; //存储组合结果
while(i >= 0 && j > 0 ){
s.push(coins[i]);
j=j-coins[i];
if(j <= 0){
break; //计算结束，退出循环
}
//如果 i == 0,那么就在第 0 行一直循环计算，直到 j=0即可
if(i>0){
//console.log(i);
while(T[i][j] == T[i-1][j]){
i--;
if(i== 0){
break;
}
}
}
}
console.log(s);
//可以把数组s return 回去
}
var coins = [1,2,5,6];
var total = 11
var n = coins.length
console.log(minCoins(coins,total,n));