递归算法解决变更问题 [英] Recursive algorithm to solve change-making problem

问题描述

我想提出一种解决变更问题的递归算法.是否可以使用一种非动态的方法，该方法不仅返回最小数量的硬币，而且还返回用于组成给定值的硬币组，

I want to make a recursive algorithm that solves the change-making problem. Is it possible to use a non-dynamic approach that not only returns the minimum number of coins but also returns the set of coins used to make-up the given value,

例如，给定值6，硬币组= [1、3、4].

For example, given the value 6 and the set of coins=[1, 3, 4]. Is it possible to make a recursive algorithm that doesn't memoise that can return both the minimum number of coins (2) and the set of coins (3,3)?

这是我当前的算法，但是它只返回硬币总数:

This is my current algorithm but it only returns the total number of coins:

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.

would return 3 but I want it to also provide the set {5, 5, 1}. The second argument (2) is the number of coins minus 1.

推荐答案

是的，这是可能的，而且非常简单.

Yes it is possible and pretty straightforward.

您只需要考虑返回的元素:这里是一个 int ，它是一个 struct(int +历史记录)以及汇总您返回的"值的函数:此处的总和(1 + int)-> int 用来跟踪历史记录修改

You just need to consider the element you return: here an int, to be a struct (int + history) and the function which aggregates your "returned" value: here the sum (1 + int)->int to track the history modification along

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 ，并同时更新历史记录.

Everywhere where you were managing the number of coin, you manage the struct.nbCoin, and you update the history alongside.

信任您，我尚未检查您的算法是否还可以.

I have not checked whether your algorithm is ok, trusting you.

我修改的代码现在对Java无效，由您来实现！

The code I modified is now not java valid, up to you to implement!

这篇关于递归算法解决变更问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！