Created
August 7, 2014 03:17
-
-
Save thepaperpilot/21eb97895b2f54d9e4f1 to your computer and use it in GitHub Desktop.
Change Combinations Calculator
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.ArrayList; | |
| import java.util.Arrays; | |
| import java.util.Collections; | |
| public class Combinations { | |
| public int combinations = 0; | |
| public int amount; | |
| public ArrayList<Integer> denominations; | |
| public static void main(String[] args) { //Example Test | |
| Combinations combinations = new Combinations(100); | |
| ArrayList<Integer> denominations = new ArrayList<Integer>(); | |
| denominations.add(1); | |
| denominations.add(5); | |
| denominations.add(10); | |
| denominations.add(25); | |
| denominations.add(50); | |
| denominations.add(100); | |
| combinations.setDenominations(denominations); | |
| System.out.println(combinations); | |
| } | |
| public Combinations(int amount) { | |
| this.amount = amount; | |
| } | |
| public void setDenominations(ArrayList<Integer> denominations) { | |
| Collections.sort(denominations); | |
| this.denominations = denominations; | |
| } | |
| public boolean calc(int amount, int lowestDenom) { | |
| if(amount == this.amount) { | |
| combinations++; | |
| return true; | |
| } else if(amount > this.amount) | |
| return true; | |
| for(Integer denom : denominations) | |
| if(denom >= lowestDenom && calc(amount + denom, denom)) | |
| break; | |
| return false; | |
| } | |
| @Override | |
| public String toString() { | |
| combinations = 0; | |
| long time = System.currentTimeMillis(); | |
| calc(0, 0); | |
| long difference = System.currentTimeMillis() - time; | |
| return "There are " + combinations + " different combinations to make " + amount + "₵ in change using the following denominations:\n" + Arrays.toString(denominations.toArray()) + "\nCalculated in " + difference + " milliseconds"; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment