WarenAutomatTest.java

private static void WechselGeldTest(Automat pAutomat) {
    
    System.out.println("=== WechselGeld-Test. =====================================");
    System.out.println("  WechselGeld moeglich: " + new WechselGeld(new ArrayList<>(Arrays.asList(10,2,5))).berechne(5));
    System.out.println("  WechselGeld moeglich: " + new WechselGeld(new ArrayList<>(Arrays.asList(1,5,10,2,5,5,3,1))).berechne(30));
    System.out.println("  WechselGeld moeglich: " + new WechselGeld(new ArrayList<>(Arrays.asList(5,5,3,1))).berechne(7));
    System.out.println("  WechselGeld moeglich: " + new WechselGeld(new ArrayList<>(Arrays.asList(1,1,1,1,2,2,2,3,3,10,5))).berechne(22));
    System.out.println("  WechselGeld moeglich: " + new WechselGeld(new ArrayList<>(Arrays.asList(1,1,1,1,1,1,5,2,2,2))).berechne(6));
    System.out.println("  WechselGeld moeglich: " + new WechselGeld(new ArrayList<>(Arrays.asList(2,10,15,7))).berechne(33));
    System.out.println("  WechselGeld moeglich: " + new WechselGeld(new ArrayList<>(Arrays.asList(1,2,3))).berechne(-1));
    System.out.println("  WechselGeld moeglich: " + new WechselGeld(new ArrayList<Integer>()).berechne(1));
    
//=== WechselGeld-Test. =====================================
//*** berechne(5), verfügbare Münzen: [10, 5, 2]
//  Münze entfernt: 5, neuer Restbetrag: 0, verfügbare Münzen: [10, 2]
//  WechselGeld moeglich: true
//*** berechne(30), verfügbare Münzen: [10, 5, 5, 5, 3, 2, 1, 1]
//  Münze entfernt: 10, neuer Restbetrag: 20, verfügbare Münzen: [5, 5, 5, 3, 2, 1, 1]
//  Münze entfernt: 5, neuer Restbetrag: 15, verfügbare Münzen: [5, 5, 3, 2, 1, 1]
//  Münze entfernt: 5, neuer Restbetrag: 10, verfügbare Münzen: [5, 3, 2, 1, 1]
//  Münze entfernt: 5, neuer Restbetrag: 5, verfügbare Münzen: [3, 2, 1, 1]
//  Münze entfernt: 2, neuer Restbetrag: 3, verfügbare Münzen: [3, 1, 1]
//  Münze entfernt: 3, neuer Restbetrag: 0, verfügbare Münzen: [1, 1]
//  WechselGeld moeglich: true
//*** berechne(7), verfügbare Münzen: [5, 5, 3, 1]
//  Münze entfernt: 1, neuer Restbetrag: 6, verfügbare Münzen: [5, 5, 3]
//  Münze entfernt: 3, neuer Restbetrag: 3, verfügbare Münzen: [5, 5]
//  WechselGeld moeglich: false
//*** berechne(22), verfügbare Münzen: [10, 5, 3, 3, 2, 2, 2, 1, 1, 1, 1]
//  Münze entfernt: 2, neuer Restbetrag: 20, verfügbare Münzen: [10, 5, 3, 3, 2, 2, 1, 1, 1, 1]
//  Münze entfernt: 10, neuer Restbetrag: 10, verfügbare Münzen: [5, 3, 3, 2, 2, 1, 1, 1, 1]
//  Münze entfernt: 5, neuer Restbetrag: 5, verfügbare Münzen: [3, 3, 2, 2, 1, 1, 1, 1]
//  Münze entfernt: 2, neuer Restbetrag: 3, verfügbare Münzen: [3, 3, 2, 1, 1, 1, 1]
//  Münze entfernt: 3, neuer Restbetrag: 0, verfügbare Münzen: [3, 2, 1, 1, 1, 1]
//  WechselGeld moeglich: true
//*** berechne(6), verfügbare Münzen: [5, 2, 2, 2, 1, 1, 1, 1, 1, 1]
//  Münze entfernt: 1, neuer Restbetrag: 5, verfügbare Münzen: [5, 2, 2, 2, 1, 1, 1, 1, 1]
//  Münze entfernt: 5, neuer Restbetrag: 0, verfügbare Münzen: [2, 2, 2, 1, 1, 1, 1, 1]
//  WechselGeld moeglich: true
//*** berechne(33), verfügbare Münzen: [15, 10, 7, 2]
//  Münze entfernt: 2, neuer Restbetrag: 31, verfügbare Münzen: [15, 10, 7]
//  Münze entfernt: 7, neuer Restbetrag: 24, verfügbare Münzen: [15, 10]
//  WechselGeld moeglich: false
//*** berechne(-1), verfügbare Münzen: [3, 2, 1]
//  WechselGeld moeglich: false
//*** berechne(1), verfügbare Münzen: []
//  WechselGeld moeglich: false
    
  }

WechselGeld.java

package warenautomat;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class WechselGeld {
  
  private List<Integer> mVerfuegbareMuenzen;
  private List<Integer> mVerwendeteMuenzen;
  private int mRestBetrag;
  
  public WechselGeld(List<Integer> pVerfuegbareMuenzen) {
    
    this.mVerfuegbareMuenzen = pVerfuegbareMuenzen;
    this.mVerwendeteMuenzen = new ArrayList<Integer>();
    
    Collections.sort(this.mVerfuegbareMuenzen);
    Collections.reverse(this.mVerfuegbareMuenzen);
    
  }
  
  public boolean berechne(int pBetrag) {
    
    System.out.println("*** berechne(" + pBetrag + "), verfügbare Münzen: " + this.mVerfuegbareMuenzen);
    
    this.mRestBetrag = pBetrag;
    int possibilities = berechne(pBetrag, this.mVerfuegbareMuenzen, 0);
    return possibilities > 0;
    
  }
  
  public List<Integer> gibVerwendeteMuenzen() {
    
    return this.mVerwendeteMuenzen;
    
  }
  
  private int berechne(int pBetrag, List<Integer> pVerfuegbareMuenzen, int pIndex) {
    
    if (pBetrag < 0 || this.mRestBetrag == 0) {
      return 0;
    }
    
    if (pBetrag == 0) {
      Integer coin = pVerfuegbareMuenzen.remove(pIndex);
      this.mVerwendeteMuenzen.add(coin);
      this.mRestBetrag -= coin;
      
      System.out.println("  Münze entfernt: " + coin + 
          ", neuer Restbetrag: " + this.mRestBetrag +
          ", verfügbare Münzen: " + this.mVerfuegbareMuenzen.toString());
      
      // Wenn eine Muenze entfernt wurde und der Restbetrag > 0, dann nochmal mit Index 0 anfangen..
      if (this.mRestBetrag > 0) {
        return berechne(this.mRestBetrag, this.mVerfuegbareMuenzen, 0);
      }
        
      return 1;
    }
    
    // Keine Muenzen mehr verfügbar
    if (pIndex == pVerfuegbareMuenzen.size() && pBetrag > 0) {
      return 0;
    }
    
    // OutOfBoundsExceptions verhindern, wegen rekursion..
    if (pIndex > pVerfuegbareMuenzen.size()) {
      return 0;
    }
    
    int restBetrag = pBetrag - pVerfuegbareMuenzen.get(pIndex);
    return berechne(restBetrag, pVerfuegbareMuenzen, pIndex) + berechne(pBetrag, pVerfuegbareMuenzen, pIndex + 1);
  }
  
}