Let's say I have the following in ArrayList of Currency like this: (But NOT in the order). Each Currency object has Bill and the count like below.
$100 10
$20 10
$10 10
$5 10
$1 10
If I need to payout an amount, how do you dispense minimum number of Bills. If it's sorted, it's easy. But if it's not sorted, what is the efficient way to do the payout? I tried with sorted and it works.
And what would be the recursion version for the payout?
This can be done with dynamic programming. It's the coin-change problem with a slight modification tracking the number of coins remaining for the current coin.
For example,
int coinChange(int[] bills, int[] count, int amount) {
int[][] solution = new int[bills.length + 1][amount + 1];
for (int i = 0; i <= bills.length; i++) {
Arrays.fill(solution[i], Integer.MAX_VALUE);
}
solution[0][0] = 0;
for (int i = 1; i <= bills.length; i++) {
for (int j = 0; j <= amount; j++) {
if (solution[i - 1][j] != Integer.MAX_VALUE) {
for (int k = 0; k <= count[i - 1] && j + bills[i - 1] * k <= amount; k++) {
solution[i][j + bills[i - 1] * k] =
Math.min(solution[i - 1][j] + 1, solution[i][j + bills[i - 1] * k]);
}
}
}
}
return solution[bills.length][amount];
}
This can be formulated recursively as:
where i represents the bill index (one-indexed), j represents the amount. The base cases are F(0, 0) = 1 and F(0, i) = ∞ for i > 0, and the solution at F(n, m). This reduces to the above dynamic programming code when properly memoized.
Tracking the exact solution instead of the number of coins in the solutions can be done the same way as the existing coin change problem, left as an exercise to the reader.