Смена монет (Динамическое программирование)

Question

У меня есть вопрос о проблеме замены монет, когда нам нужно не только напечатать количество способов изменить $n с заданными номиналами монет, например, {1,5,10,25}, но также распечатать способы

Например, если цель = 50 долларов, а монеты {1,5,10,25}, то способы на самом деле использовать монеты, чтобы получить цель

• 2 × 25 долларов
• 1 × $25 + 2 × $10 + 1 × $5
• и т.п.

Какова лучшая временная сложность, которую мы могли бы решить, чтобы решить эту проблему? Я попытался изменить решение динамического программирования для задачи смены монет, где нам нужно только количество способов, но не фактические способы

У меня проблемы с определением сложности времени. Я использую запоминание, чтобы мне не пришлось снова решать ту же проблему для данной монеты и суммы, но все же нам нужно перебрать все решения и распечатать их. Таким образом, временная сложность определенно больше, чем O(ns), где n - количество монет, а s - цель. Это экспоненциально? Любая помощь будет высоко ценится

Answer 1

Печать комбинаций

def coin_change_solutions(coins, S):
  # create an S x N table for memoization
  N = len(coins)
  sols = [[[] for n in xrange(N + 1)] for s in xrange(S + 1)]
  for n in range(0, N + 1):
    sols[0][n].append([])

  # fill table using bottom-up dynamic programming
  for s in range(1, S+1):
    for n in range(1, N+1):
      without_last = sols[s][n - 1]
      if (coins[n - 1] <= s):
          with_last = [list(sol) + [coins[n-1]] for sol in sols[s - coins[n - 1]][n]]
      else:
          with_last = []
      sols[s][n] = without_last + with_last

  return sols[S][N]


print coin_change_solutions([1,2], 4)
# => [[1, 1, 1, 1], [1, 1, 2], [2, 2]]

• без: нам не нужно использовать последнюю монету, чтобы сделать сумму. Все решения для монет можно найти непосредственно в solution[s][n-1], Мы берем все эти комбинации монет и копируем их в with_last_sols,

• с: нам нужно использовать последнюю монету. Так что эта монета должна быть в нашем решении. Остальные монеты можно найти рекурсивно через sol[s - coins[n - 1]][n], Чтение этой записи даст нам много возможных вариантов того, какими должны быть оставшиеся монеты. Для каждого возможного выбора sol добавляем последнюю монету, coin[n - 1]:

  # For example, suppose target is s = 4
  # We're finding solutions that use the last coin.
  # Suppose the last coin has a value of 2:
  #
  # find possible combinations that add up to 4 - 2 = 2: 
  # ===> [[1,1], [2]] 
  # then for each combination, add the last coin 
  # so that the combination adds up to 4)
  # ===> [[1,1,2], [2,2]]
  

Окончательный список комбинаций можно найти, взяв комбинации для первого и второго случая и объединив два списка.

without_last_sols = [[1,1,1,1]]
with_last_sols = [[1,1,2], [2,2]]
without_last_sols + with_last_sols = [[1,1,1,1], [1,1,2], [2,2]]

---

Сложность времени

В худшем случае у нас есть набор монет со всеми монетами от 1 до n: coins = [1,2,3,4,..., n] - количество возможных комбинаций сумм монет, num решений, равно количество целочисленных разбиений s, p (s). Можно показать, что число целочисленных разбиений p (s) растет в геометрической прогрессии.
Следовательно, num solutions = p (s) = O(2^s). Любое решение должно иметь это как минимум, чтобы распечатать все эти возможные решения. Следовательно, проблема носит экспоненциальный характер.

У нас есть два цикла: один цикл для s и другой цикл для n.
Для каждого s и n мы вычисляем sols[s][n]:

• без: Мы смотрим на комбинации O(2^s) в sol[s - coins[n - 1]][n], Для каждой комбинации мы копируем ее за O(n) раз. В общем, это занимает: O(n×2^s) времени.
• с: Мы смотрим на все комбинации O(2^s) в sol[s][n], Для каждого списка комбинаций sol, мы создаем копию этого нового списка за O(n) время и затем добавляем последнюю монету. В целом этот случай занимает O(n×2^s).

Следовательно, временная сложность составляет O(s×n)×O(n2^s + n2^s) = O(s×n^2×2^s).

---

Космическая сложность

Сложность пространства составляет O (s × n ^ 2 × 2 ^ s), потому что у нас есть таблица × n с каждой записью, хранящей O(2^s) возможных комбинаций (например, [[1, 1, 1, 1], [1, 1, 2], [2, 2]]), с каждой комбинацией (например, [1,1,1,1]) занимая O(n) пространство.

Answer 2

Пусть d_i деноминация, стоимость монеты в центах. В вашем примере d_i = {1, 5, 10, 25}. Пусть k будет количеством купюр (монет), здесь k = 4.

Мы будем использовать двумерный массив numberOfCoins[1..k][0..n], чтобы определить минимальное количество монет, необходимое для внесения изменений. Оптимальное решение дает:

numberOfCoins[k][n] = min(numberOfCoins[i − 1][j], numberOfCoins[i][j − d_i] + 1)

Вышеупомянутое уравнение отражает тот факт, что для построения оптимального решения мы либо не используем d_i, поэтому нам нужно использовать меньшую монету (вот почему i уменьшается ниже):

numberOfCoins[i][j] = numberOfCoins[i − 1][j]   // eq1

или мы используем d_i, поэтому мы добавляем +1 к нужному количеству монет и уменьшаем на d_i (значение только что использованной монеты):

numberOfCoins[i][j] = numberOfCoins[i][j − d_i] + 1   // eq2

Сложность по времени составляет O (kn), но в случаях, когда k мало, как в вашем примере, мы имеем O(4n) = O(n).

Мы будем использовать другой двумерный массив coinUsed, имеющий те же размеры, что и numberOfCoins, чтобы отметить, какие монеты были использованы. Каждая запись либо скажет нам, что мы не использовали монету в coinUsed[i][j], установив "^" в этой позиции (это соответствует eq1). Или мы отмечаем, что монета использовалась, устанавливая "<" в этой позиции (соответствует eq2).

Оба массива могут быть построены, поскольку алгоритм работает. У нас будет только постоянное количество инструкций во внутреннем цикле, поэтому временная сложность построения обоих массивов по-прежнему равна O (kn).

Чтобы напечатать решение, нам нужно выполнить итерацию, в худшем случае, по k + n+1 элементам. Например, когда оптимальным решением является использование всех 1 центов. Но обратите внимание, что печать выполняется после сборки, поэтому общая сложность времени составляет O(kn) + O(k + n+1). Как и раньше, если k мало, то сложность O(kn) + O(k + n+1) = O(kn) + O(n+1) = O(kn) + O(n) = O((k+1)n) = O(n).

Answer 3

Я обычно рекурсивно решаю проблему, а затем создаю решение для запоминания.

Начиная с рекурсивного, подход прост, выберите монету, отнимите от цели и не выбирайте монету.

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

void print(vector<int>& coinsUsed)
{
    for(auto c : coinsUsed)
    {
        cout << c << ",";
    }
    cout << endl;
}

int helper(vector<int>& coins, int target, int index, vector<int>& coinsUsed)
{
    if (index >= coins.size() || target < 0) return 0;

    if (target == 0)
    {
        print(coinsUsed);
        return 1;
    }

    coinsUsed.push_back(coins[index]);
    int with = helper(coins, target - coins[index], index, coinsUsed);

    coinsUsed.pop_back();
    int without = helper(coins, target, index + 1, coinsUsed);

    return with + without;
}

int coinChange(vector<int>& coins, int target)
{
    vector<int> coinsUsed;
    return helper(coins, target, 0, coinsUsed);
}

Вы можете назвать это как:

vector<int> coins = {1,5,10,25};
cout << "Total Ways:" << coinChange(coins, 10);

Таким образом, это дает вам общее количество способов, а также монет, используемых в процессе для достижения цели, хранящейся в coinsUsed теперь вы можете запомнить это, как вам угодно, сохраняя переданные значения в кеше.

Временная сложность рекурсивного решения является экспоненциальной.

ссылка на работающую программу: http://coliru.stacked-crooked.com/a/5ef0ed76b7a496fe