Correct recursive backtracking algorithm?
My purpose is to find a way to display all the possible ways of reverting changes for a given value, with the values being checked in the file txt
. This must be achieved with Recursive Backtracking or my solution will not be provided. I'll be honest that I completely lost how to code the corresponding algorithm. All I know is that the algorithm works something like this:
start with empty sets.
add a dime to one set.
subtract '10' from my amount.
This is a negative number, so I discard that set: it is invalid.
add a nickel to another (empty) set.
subtract '5' from my amount.
This equals 2; so I'll have to keep working on this set.
Now I'm working with sets that already include one nickel.
add a dime to one set.
subtract '10' from my amount.
This is a negative number, so I discard that set: it is invalid.
repeat this with a nickel; I discard this possibility because (2 - 5) is also negative.
repeat this with a penny; this is valid but I still have 1 left.
repeat this whole process again with a starting set of one nickel and one penny,
again discarding a dime and nickel,
and finally adding a penny to reach an amount of 0: this is a valid set.
Now I go back to empty sets and repeat starting with a nickel, then pennies.
The problem is that I have no idea how or where to start, just what needs to be done or if any other solutions are obvious.
This is my code:
UPDATED
import java.io.*;
import java.util.*;
import java.lang.*;
public class homework5 {
public static int penny = 1;
public static int nickle = 5;
public static int dime = 10;
public static int quarter = 25;
public static int halfDollar = 50;
public static int dollar = 100;
public static int change;
public static void main(String[] args) throws FileNotFoundException {
ArrayList<Integer> coinTypes = new ArrayList<Integer>();
Integer i;
File f = new File (args[0]);
Scanner input = new Scanner(f);
input.nextLine();
while(input.hasNextInt()) {
i = input.nextInt();
coinTypes.add(i);
}
change = coinTypes.get(coinTypes.size()-1);
coinTypes.remove(coinTypes.size()-1);
System.out.println("Found change"); //used for debugging
System.out.println("Change: " + change);
System.out.println(coinTypes);
}
boolean findChange(int change, List<Integer> coinTypes,
List<Integer> answerCoins) {
if(change == 0) {
return true;
}
if(change < 0) {
return false;
} else {
for(Integer coin : coinTypes) {
if(findChange(change - coin, coinTypes, answerCoins)){
answerCoins.add(coin);
return true;
}
}
List<Integer> answer = new ArrayList<Integer>();
boolean canFindChange = findChange(change, coinTypes, answer);
if(canFindChange) {
System.out.println(answer);
} else { System.out.println("No change found");
}
return false;
}
}
Here is the input file that I scan into
java homework5 hwk5sample1.txt
// Coins available in the USA, given in cents. Change for $1.43?
1 5 10 25 50 100
143
OUTPUT
Found change
Change: 143
[1, 5, 10, 25, 50, 100]
So using the numbers in mine coinTypes
ArrayList
, I need a generic code algorithm to show all the possible ways to get, for example 143 ($ 1.43) back with changes, using coins in a file with all pennies is the last way to show this.
Please do not think that I want you to push me the algorithm, I just want to help write, otherwise I will not know anything. Thanks everyone for any answers or help you can give, it means a lot to me! Please let me know if I missed anything or if you need more information.
source to share
The example you are going through seems to be mostly correct. The only mistake: again discarding a dime and nickel
which should be again discarding a *penny* and nickel
(but I think it's just a typo.)
To write a recursive backtracking algorithm, it is helpful to think of the recursive call as a solution to a subproblem of the original problem. In one possible implementation of the solution, the pseudocode looks like this:
/**
* findChange returns true if it is possible to make *change* cents of change
* using the coins in coinTypes. It adds the solution to answerCoins.
* If it impossible to make this amount of change, then it returns false.
*/
boolean findChange(int change, List<Integer> coinTypes, List<Integer> answerCoins) {
if change is exactly 0: then we're done making change for 0 cents! return true
if change is negative: we cannot make change for negative cents; return false
otherwise, for each coin in coinTypes {
// we solve the subproblem of finding change for (change - coin) cents
// using the recursive call.
if we can findChange(change - coin, coinTypes, answerCoins) {
// then we have a solution to the subproblem of
// making (change - coins) cents of change, so:
- we add coin to answerCoins, the list of coins that we have used
- we return true // because this is a solution for the original problem
}
}
//if we get to the next line, then we can't find change for any of our subproblems
return false
}
We will call this method as follows:
List<Integer> answer = new ArrayList<Integer>();
boolean canFindChange = findChange(change, coinTypes, answer);
if(canFindChange) {
System.out.println(answer); // your desired output.
}
else {
System.out.println("Can't find change!");
}
source to share