CODEWITHSUNDEEP
javaalgorithmloopssortingobject
Kevin Rave
Kevin Rave

Reputation: 14456

Cash Dispense logic - Java

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?

Upvotes: 0

Views: 562

Answers (1)

kevmo314
kevmo314

Reputation: 4317

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:

enter image description here

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.

Upvotes: 1

Related Questions