I am practicing Java and I was trying to create a program to calculate the amount of ways an number could be divided using a set number of dividers.
For instance:
100 is the number and the dividers are 50,20,5. What are the possible divisions.
The answer would be:
Amount of 50 : 0, Amount of 20 : 0, Amount of 10 : 10
Amount of 50 : 0, Amount of 20 : 1, Amount of 10 : 8
Amount of 50 : 0, Amount of 20 : 2, Amount of 10 : 6
Amount of 50 : 0, Amount of 20 : 3, Amount of 10 : 4
Amount of 50 : 0, Amount of 20 : 4, Amount of 10 : 2
Amount of 50 : 1, Amount of 20 : 0, Amount of 10 : 5
Amount of 50 : 1, Amount of 20 : 1, Amount of 10 : 3
Amount of 50 : 1, Amount of 20 : 2, Amount of 10 : 1
Amount of 50 : 2
I wrote a code that asks the user an amount and 3 dividers. Now I am trying to figure out if there is a way to dynamically create a code for as many dividers as the user wants. The code is in a way very repetitive and there is a certain pattern to add another divider but I cannot figure out how to implement this dynamic change to the code.
The first code I came up with to do this is the following:
public class Test2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Insert the amount:");
int amount = scanner.nextInt();
List<Integer> dividers = new ArrayList<>();
System.out.println("Insert the first divider:");
int tempDivider = scanner.nextInt();
if (!dividers.contains(tempDivider)) {
dividers.add(tempDivider);
}
while (dividers.size()<3) {
System.out.println("Insert the next divider: (" + (3-dividers.size()) + " more to go)");
tempDivider = scanner.nextInt();
if (!dividers.contains(tempDivider)) {
dividers.add(tempDivider);
}
}
dividers.sort(Collections.reverseOrder());
System.out.print("Dividers are: ");
System.out.println(dividers);
int getal1 = dividers.get(0);
int getal2 = dividers.get(1);
int getal3 = dividers.get(2);
int fiftyAmount = amount / getal1;
int fiftyRemainder = amount % getal1;
for (int i = 0; i <= fiftyAmount; i++) {
int currentFiftyAmount = amount - (getal1 * i);
int twentyAmount = currentFiftyAmount / getal2;
int twentyRemainder = currentFiftyAmount % getal2;
if (twentyAmount == 0) {
StringBuilder output = new StringBuilder();
output.append("Amount of " + getal1 + " banknotes: " + i);
if (fiftyRemainder != 0) output.append(", Remainder: " + fiftyRemainder);
System.out.println(output);
} else {
for (int j = 0; j <= twentyAmount; j++) {
int currentTwentyAmount = currentFiftyAmount - (getal2 * j);
int tenAmount = currentTwentyAmount / getal3;
int tenRemainder = currentTwentyAmount % getal3;
if (tenAmount == 0) {
StringBuilder output = new StringBuilder();
output.append("Amount of " + getal1 + " banknotes: " + i + ", Amount of " + getal2 + " banknotes: " + j);
if (tenRemainder != 0) output.append(", Remainder: " + twentyRemainder);
} else {
StringBuilder output = new StringBuilder();
output.append("Amount of " + getal1 + " banknotes: " + i + ", Amount of " + getal2 + " banknotes: " + j +
", Amount of " + getal3 + " banknotes: " + tenAmount);
if (tenRemainder != 0) output.append(", Remainder: " + tenRemainder);
System.out.println(output);
}
}
}
}
}
}
I tried to make this more abstract to figure out a way to automate the creation of the extra dividing loops but I cannot figure it out. The more abstract version I wrote is the following:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Insert the amount:");
int amount = scanner.nextInt();
List<Integer> dividers = new ArrayList<>();
System.out.println("Insert the first divider:");
dividers.add(scanner.nextInt());
int divider;
while (dividers.size()<2) {
System.out.println("Insert the next divider: (" + (2-dividers.size()) + " more to go)");
divider = scanner.nextInt();
if (!dividers.contains(divider)) {
dividers.add(divider);
}
}
dividers.sort(Collections.reverseOrder());
System.out.print("Dividers are: ");
System.out.println(dividers);
int divided1Amount = amount / dividers.get(0);
int divided1Remainder = amount % dividers.get(0);
for (int i = 0; i <= divided1Amount; i++) {
int currentDivided1Amount = amount - (dividers.get(0) * i);
int divided2Amount = currentDivided1Amount / dividers.get(1);
int divided2Remainder = currentDivided1Amount % dividers.get(1);
if (divided2Amount == 0) {
StringBuilder output = new StringBuilder();
output.append(dividers.get(0) + ":" + i);
if (divided1Remainder != 0) {
output.append(", Remainder: " + divided1Remainder);
}
System.out.println(output);
} else {
StringBuilder output = new StringBuilder();
output.append(dividers.get(0) + ":" + i + "," + dividers.get(1) + ":" + divided2Amount);
if (divided2Remainder != 0) {
output.append(", Remainder: " + divided2Remainder);
}
System.out.println(output);
}
}
}
}
This is also available on GitHub: https://github.com/realm1930/rekendin/blob/master/src/Main.java
Could anybody please enlighten me. I am sorry if I am not clear at my description of the issue.
Thanks
While a fixed number of dividers can be well approached with nested loops, I suggest for the general case to write the solution as a recursive function.
This problem is a good fit for dynamic programming. What I mean by this is that the problem can be broken down into simpler subproblems, and in this way the solution is naturally implemented with recursion. For instance, in your example of expressing 100 as a sum of multiples of 50, 20, and 10, there are three solutions found that all use one 50:
Amount of 50 : 1, Amount of 20 : 0, Amount of 10 : 5
Amount of 50 : 1, Amount of 20 : 1, Amount of 10 : 3
Amount of 50 : 1, Amount of 20 : 2, Amount of 10 : 1
Look at this as solving the subproblem of finding the ways that value 50 can be expressed as multiples of 20 and 10 (that is, 50 is equal to 20*0 + 10*5, 20*1 + 10*3 and 20*2 + 10*1). So you can divide-and-conquer the original problem in this sense.
Let X be the number (e.g. 100) to express, and D1, D2, ... DN the dividers. Here is a possible outline:
If there is just one divider, N = 1, it is easy: there just zero or one solution depending on whether D1 divides X.
Otherwise, possible solutions might have D1 with any multiple from 0, 1, ..., X/D1. So make a loop m1 = 0, 1, ..., X/D1, and recursively solve the subproblem having X' = X - m1*D1 and the remaining dividers D2, ..., DN. This subproblem has one fewer divider, so after enough recursions it reduces to the N = 1 case.
That solves the problem. Note, though, that fully recursing may result in a combinatorially vast number of subproblems to solve. So for efficient solution it is a good idea to store or "memoize" the solutions of previously-solved subproblems in a table so that work isn't repeated.
Other thoughts:
Let Q be the greatest common divisor (GCD) of all the dividers {D1, ..., DN}. If X isn't divisible by Q, then there are no solutions, in which case we can skip the above recursive search entirely. E.g. there is no way to express X = 103 with dividers 50, 20, and 10. This GCD test can also be applied to every subproblem so that some recursive calls can return early.
This problem is a kind of Diophantine equation, more specifically, it is related to the Frobenius coin problem and Frobenius numbers. There is a mathoverflow post discussing it.