Рекурсивный алгоритм для решения проблемы изменения

Question

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

Например, учитывая значение 6 и набор монет = [1, 3, 4]. Можно ли создать рекурсивный алгоритм, который не запоминает, который может возвращать как минимальное количество монет (2), так и набор монет (3,3)?

РЕДАКТИРОВАТЬ: Это мой текущий алгоритм, но он возвращает только общее количество монет:

int makeChangeRecursive(int[] coins, int numCoins, int amount)
   int r, l;
   if (A == 0) return 0;
   else if (n == -1 || A < 0) return -1;
   r = makeChangeRecursive(coins, numCoins - 1, amount);
   l = 1 + makeChangeRecursive(coins, numCoins, amount - coins[numCoins]);
   if (r == -1 && l == 0) return -1;
   else if ((r == -1 || l < r) && l != 0) return l;
   return r;

makeChangeRecursive({1, 2, 5}, 2, 11);

вернул бы 3, но я хочу, чтобы он также предоставил набор {5, 5, 1}. Второй аргумент (2) - количество монет минус 1.

Answer 1

Да, это возможно и довольно просто.

Вам просто нужно учитывать возвращаемый элемент: здесь int, struct (int + history) и функцию, которая объединяет ваше «возвращенное» значение: здесь сумма (1 + int)->int для отслеживания изменения истории по

int -> 1 + int
// becomes
(int, history) -> (int+1, history + pieceTaken)

Рассмотрим структуру

struct NbCoin {
  int nbCoin;
  vector<int> history; // array of pieces you took during recursion
}

//now makeChangeRecursive returns the number of coin AND history
NbCoin makeChangeRecursive(int[] coins, int numCoins, int amount)
    int r, l;
    if (A == 0) return { nbCoin: 0, history: []}; //like before but with the empty history
    else if (n == -1 || A < 0) return { nbCoin: -1, history: []}; // idem

    // now contains our history as well
    r = makeChangeRecursive(coins, numCoins - 1, amount);

    // here you are taking some coin, so track it into history
    l = makeChangeRecursive(coins, numCoins, amount - coins[numCoins]);
    l = { 
      nbCoin: 1 + l.nbCoin, // like before
      history : l.history.concat(coins[numCoins]) // pieceTaken is coins[numCoins]
      // concat should create a __new__ array merging l.history and coins[numCoins]
    }

    // put nbCoin everywhere as our comparison key
    if (r.nbCoin == -1 && l.nbCoin == 0) return { nbCoin: -1, []};
    else if ((r.nbCoin == -1 || l.nbCoin < r.nbCoin) && l.nbCoin != 0) return l;
    return r;

makeChangeRecursive({1, 2, 5}, 2, 11);

Везде, где вы управляли количеством монет, вы управляете struct.nbCoin, и вы обновляете историю вместе с ним.

Я не проверял, в порядке ли ваш алгоритм, доверяя вам.

Код, который я изменил, теперь не java действителен, до вас!