解决找零问题的递归算法
Recursive algorithm to solve change-making problem
我想做一个递归算法来解决找零问题。是否可以使用一种非动态方法,不仅 return 是最小硬币数量,而且 return 是用于构成给定值的一组硬币,
例如,给定值 6 和一组硬币 = [1, 3, 4]。是否有可能制作一个不记忆的递归算法,它可以 return 最小硬币数 (2) 和硬币组 (3,3)?
编辑:这是我当前的算法,但它只有 return 硬币总数:
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);
会 return 3 但我希望它也提供集合 {5, 5, 1}。第二个参数(2)是硬币个数减1。
是的,这是可能的,而且非常简单。
您只需要考虑您 return 的元素:这里是 int
,是 struct (int + history)
以及汇总您的 "returned" 值的函数:这里的总和 (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无效,由你实现!
我想做一个递归算法来解决找零问题。是否可以使用一种非动态方法,不仅 return 是最小硬币数量,而且 return 是用于构成给定值的一组硬币,
例如,给定值 6 和一组硬币 = [1, 3, 4]。是否有可能制作一个不记忆的递归算法,它可以 return 最小硬币数 (2) 和硬币组 (3,3)?
编辑:这是我当前的算法,但它只有 return 硬币总数:
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);
会 return 3 但我希望它也提供集合 {5, 5, 1}。第二个参数(2)是硬币个数减1。
是的,这是可能的,而且非常简单。
您只需要考虑您 return 的元素:这里是 int
,是 struct (int + history)
以及汇总您的 "returned" 值的函数:这里的总和 (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无效,由你实现!