Проблема смены монет с бесконечным количеством монет каждого достоинства

Question

Я хочу знать идею алгоритма для задачи смены монет, где у каждого достоинства есть бесконечное количество монет. Означает, как применить DP (например, стандартная проблема смены монет) Например, в наборе 1,10,15, Размен на 35 дает - 2 монеты 10 и одна монета 15

Также дайте мне представление об алгоритме перебора. Я знаю, чтобы перебрать все наборы. Но как изменить количество каждой монеты при грубом форсировании

Answer 1

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

Доступны монеты 1c, 5c, 10c, 25c (их можно настроить в соответствии с вашими потребностями)

1. Минимальные монеты для 1c = 1 X 1c. До 4 центов нам нужны монеты 1с, так как это наименее номинал.
2. Для 5 центов у нас есть одна 5c монета. Объединяя это с 4c выше, мы можем генерировать любое число от 1 до 9.
3. Для 10 центов нам нужен 1 X 10c. Комбинируя вышеперечисленные три, мы можем сгенерировать любое число от 1 до 19.
4. Для 20c нам нужно 2 x 10c, так как 20 делится на 10.

Если вы можете сформулировать проблему индуктивно, возможно, вам будет легче ее решить.

EDIT:
Хорошо, вот еще одна попытка объяснить решение динамического программирования:

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

строка 1 представляет собой набор {1c}, т. Е. В строке 1 вам разрешено использовать бесконечный 1c
строка 2 представляет набор {1c, 10c}, т.е. в строке 2 вам разрешено бесконечное число 1c и 10c
строка 3 представляет набор {1c, 10c, 15c} и так далее ...
Каждый столбец представляет сумму, которую вы хотите построить.

Таким образом, каждая ячейка соответствует одной маленькой подзадаче. Например (для простоты индексы начинаются с 1),
cell(1, 5) ==> построить 5c используя только {1c}
cell(2, 9) ==> построить 9c используя {1c, 10c}
cell(3, 27) ==> построить 27c используя {1c, 10c, 15c}
Теперь ваша цель - получить ответ на cell(x, n)

Solution:
Начните решать таблицу с самой простой задачи. Решение первого ряда тривиально, так как в первом ряду единственное доступное наименование - {1c}. Каждая клетка в строке 1 имеет тривиальное решение, приводящее к cell(1, n) = {nx1c} (n монет 1c).

Теперь перейдите к следующему ряду. Обобщая для 2-й строки, давайте посмотрим, как решить для (скажем) cell(2, 28), то есть построить 28c с использованием {1c, 10c}. Здесь вам необходимо принять решение, включать ли в решение 10c или нет, и сколько монет. У вас есть 3 варианта (3 = 28/10 + 1)

Choice 1
Возьмите {1x10c} и остаток от предыдущего ряда (который хранится в cell(1, 18)). Это дает вам {1x10c, 18x1c} = 19 coins

Choice 2
Возьмите {2x10c} и остаток от предыдущего ряда (который хранится в cell(1, 8)). Это дает вам {2x10c, 8x1c} = 10 coins

Choice 3
Возьмите не 10c и остаток от предыдущего ряда (который хранится в cell(1, 28)). Это дает вам {28x1c} = 28 coins

Очевидно, что выбор 2 - лучший, так как требует меньше монет. Запишите это в таблицу и продолжайте. Таблица должна быть заполнена по одной строке за раз и внутри строки в порядке возрастания суммы.

Следуя приведенным выше правилам, вы достигнете cell(x, n), решением которого будет выбор между n/p + 1 альтернативами, где p = новейшее наименование в строке x. Лучший выбор - ваш ответ.

Таблица на самом деле запоминает решения небольших проблем, поэтому вам не нужно решать их снова и снова.

Answer 2

о грубой силовой части:

int i,j,k;
for(i=0;i<35;i++){
  for(j=0;j<4;j++){
    for(k=0;k<3;k++){
      if(1*i+10*j+15*k == 35){
        //is this what you need?
        //minimum=min(minimum,(i+j+k));
      }
    }
  }
}

Answer 3

Вы можете запустить его здесь http://www.exorithm.com/algorithm/view/coin_change

function coin_change ($amount, $coins)
{
  $change = array();
  rsort($coins);
  for($i=0; $i<count($coins); $i++) {
    $change[$coins[$i]] = floor($amount/$coins[$i]);
    $amount = $amount % $coins[$i];
  }
  return $change;
}

Answer 4

Это способ перевода номера из одной системы нумерации в другую. Например:

35 = 1*2^5 + 0*2^4 + 0*2^3 + 0*2^2 + 0*2^1 + 1*2^0

То есть:

var cash = 35;
var coins = [15, 10, 5, 1];
var change = {};
for(var i=0; i<coins.length; i++){
  change[coins[i]]  = Math.floor(cash/coins[i]);
  cash %= coins[i];
}
//change now contains:
//15:2, 10:0, 5:1, 1:0

Answer 5

Относительно грубой силы.

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

псевдокод, возвращает количество монет, необходимое для представления стоимости, если мы можем использовать каждую бесконечное число раз

int[] greedy(int value, int[] coins) {
   int[] ans = ...;
   int v = coins.length - 1;
   int left = value;
   while (left > 0 && v >= 0) {
       if (coins[v] <= left) {
           ans.push(coins[v]);
       } else { 
           v--;
       }
   }
   return left == 0 ? ans : //representation impossible, 
                            //so you better do something;
}

псевдокод, возвращает количество монет, необходимое для представления стоимости, если мы можем использовать каждую бесконечное число раз

int f(int value, int[] coins) {
   int[] memo = new int[value + 1];
   Arrays.fill(memo, 1234567);
   memo[0] = 0;
   for (int coin : coins)
       for (int i = 0; i + coin <= value; i++)
           memo[i + coin] = min(memo[i + coin], memo[i] + 1);
   return memo[value];
}

чтобы узнать, какие монеты взять, начните с конца: if memo[value] = 3, затем вы проверяете все монеты и находите такую ​​монету, что memo[value - coin] == 2, продолжаете с (value - coin) до достижения 0.