Im stuck at this problem about the change of a vending machine (using 10ct, 20 ct, 50ct, 100ct and 200ct-coins.)

So lets say coffee costs 40cts. The user throws in 2€ (labeled 200cts).

Now im supposed to figure out how the change of 160cts is given back to the user. There are 2 conditions: A) Taking the shortest combination, but B) only if the register has enough coins to hand out said combination .

So in my example, the shortest combination is 100cts + 50cts + 10cts. But if, lets say, there are no 10ct coins left in the register, the prefered combination should be 100ct + 20ct + 20ct + 20ct.

public void coinChange (int change) { int TwoEuroCount = 0, OneEuroCount= 0, FiftyCentsCount = 0, TwentyCentsCount = 0, TenCentsCount = 0; while (change > 0) { TwoEuroCount = change / 200; if(register.availableTwoEuros(TwoEuroCount) == true) { register.withdrawTwoEuros(TwoEuroCount); change = change - 200 * TwoEuroCount; //the method .availableTwoEuros returns true if AmountOfTwoEuros - TwoEuroCount >= 0 } OneEuroCount = change / 100; if(register.availableOneEuro(OneEuroCount) == true) { register.withdrawOneEuro(OneEuroCount); change = change - 100 * OneEuroCount; } FiftyCentsCount = change / 50; if(register.availableFiftyCents(FiftyCentsCount) == true) { register.withdrawFiftyCents(FiftyCentsCount); change = change - 50 * FiftyCentsCount; } TwentyCentsCount = change / 20; if (register.availableTwentyCents(TwentyCentsCount) == true) { register.withdrawTwentyCents(TwentyCentsCount); change = change - 20 * TwentyCentsCount; } TenCentsCount = change / 10; if(register.availableTenCents(TenCentsCount) == true) { register.withdrawTenCents(TenCentsCount); change = change - 10 * TenCentsCount; } } }

This works perfectly for finding the shortest combination if there are enough coins. But if i start with AmountTenCents = 0, the method will just take 1 Euro and 50cts and leave it at that.

Suppose you have:

- an array of all possible coin
`VALUES`

: [10, 20, 50, 100, 200] - an array of the current
`SUPPLY`

of coins for each`VALUE`

- an array of
`WEIGHS`

that correspond to`VALUES`

(higher weigh, smaller value): [4, 3, 2, 1, 0]

then you could find a **combination** of coins that sums up to **change** and has the minimum total **weight**.

Let a combination `c`

be the current combination of coins. For example, `c = [0, 1, 1, 2, 0]`

would mean that you are considering a combination where you have **no** 10 cent coins, **one** 20 cent coin, **one** 50 cent coin, **two** 1€ coins and **no** 2€ coins.

You begin with combination `c = [0, 0, 0, 0, 0]`

.

Using weights will implicitly assure you that the resulting combination will have the minimum weight and is thus the result you are looking for. For example:

// Both combinations represent the change of 160 cents c = [1, 0, 1, 1, 0] => weight: 4*1 + 3*0 + 1*2 + 1*1 + 0*0 = 7 c = [0, 3, 0, 1, 0] => weight: 4*0 + 3*3 + 0*2 + 1*1 + 0*0 = 10

Something like this should work:

import java.util.Arrays; import java.util.stream.IntStream; public class Change { /** The number of unique coins. */ static final int N = 5; static final int[] VALUES = { 10, 20, 50, 100, 200 }; static final int[] WEIGHTS = { 4, 3, 2, 1, 0 }; static final int[] SUPPLY = { 10, 35, 40, 100, 2 }; static int[][] result = { { // The minimum weight Integer.MAX_VALUE }, { // The resulting combination of coins 0, 0, 0, 0, 0 } }; public static void main(String[] args) { int change = 160; solve(new int[N], change); if (result[0][0] == Integer.MAX_VALUE) { System.out.println( "Can't return the change with the given SUPPLY of coins" ); } else { System.out.println(Arrays.toString(result[1])); } } static void solve(int[] c, int change) { // check if out of supply boolean isOutOfSupply = IntStream.range(0, N).anyMatch(i -> SUPPLY[i] < c[i]); if (isOutOfSupply) return; // compute weight int weight = IntStream.range(0, N).map(i -> WEIGHTS[i] * c[i]).sum(); // compute sum int sum = IntStream.range(0, N).map(i -> VALUES[i] * c[i]).sum(); if (sum == change && weight < result[0][0]) { result[0][0] = weight; result[1] = c; } else if (sum < change) { IntStream.range(0, N).forEach(i -> solve(increment(c, i), change)); } } static int[] increment(int[] array, int index) { int[] clone = array.clone(); clone[index]++; return clone; } }

## Recent Comments