递归找零:如何修改我的算法来打印所有的组合? [英] Making change recursively: How do I modify my algorithm to print all combinations?
本文介绍了递归找零:如何修改我的算法来打印所有的组合?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有一种算法,递归使得变化以下述方式:
I have an algorithm that recursively makes change in the following manner:
public static int makeChange(int amount, int currentCoin) {
//if amount = zero, we are at the bottom of a successful recursion
if (amount == 0){
//return 1 to add this successful solution
return 1;
//check to see if we went too far
}else if(amount < 0){
//don't count this try if we went too far
return 0;
//if we have exhausted our list of coin values
}else if(currentCoin < 0){
return 0;
}else{
int firstWay = makeChange(amount, currentCoin-1);
int secondWay = makeChange(amount - availableCoins[currentCoin], currentCoin);
return firstWay + secondWay;
}
}
不过,我想增加存储或打印的各种组合,因为他们成功返回的能力。我有一个有点很难包装我的头,围绕如何做到这一点。原来的算法是pretty的容易,但现在我很沮丧。有什么建议?
However, I'd like to add the capability to store or print each combination as they successfully return. I'm having a bit of a hard time wrapping my head around how to do this. The original algorithm was pretty easy, but now I am frustrated. Any suggestions?
CB
推荐答案
我用下面的:
/**
* This is a recursive method that calculates and displays the combinations of the coins included in
* coinAmounts that sum to amountToBeChanged.
*
* @param coinsUsed is a list of each coin used so far in the total. If this branch is successful, we will add another coin on it.
* @param largestCoinUsed is used in the recursion to indicate at which coin we should start trying to add additional ones.
* @param amountSoFar is used in the recursion to indicate what sum we are currently at.
* @param amountToChange is the original amount that we are making change for.
* @return the number of successful attempts that this branch has calculated.
*/private static int change(List<Integer> coinsUsed, Integer currentCoin, Integer amountSoFar, Integer amountToChange)
{
//if last added coin took us to the correct sum, we have a winner!
if (amountSoFar == amountToChange)
{
//output
System.out.print("Change for "+amountToChange+" = ");
//run through the list of coins that we have and display each.
for(Integer count: coinsUsed){
System.out.print(count + " ");
}
System.out.println();
//pass this back to be tallied
return 1;
}
/*
* Check to see if we overshot the amountToBeChanged
*/
if (amountSoFar > amountToChange)
{
//this branch was unsuccessful
return 0;
}
//this holds the sum of the branches that we send below it
int successes=0;
// Pass through each coin to be used
for (Integer coin:coinAmounts)
{
//we only want to work on currentCoin and the coins after it
if (coin >= currentCoin)
{
//copy the list so we can branch from it
List<Integer> copyOfCoinsUsed = new ArrayList<Integer>(coinsUsed);
//add on one of our current coins
copyOfCoinsUsed.add(coin);
//branch and then collect successful attempts
successes += change(copyOfCoinsUsed, coin, amountSoFar + coin, amountToChange);
}
}
//pass back the current
return successes;
}
这篇关于递归找零:如何修改我的算法来打印所有的组合?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文