货币组合问题的实现

问题：
有1元,5元,10元,50元,100元的五种货币,任给定一个数额,求所有可能的组合数.

 

思路：
是用排列组合中思想做出的一个计算所有排列数量的算法
思想是,数额321,以100元单位为例,总组合数量是下面两种情况之和:
1.组合里包含100元,即至少有100元1张,那么321-100=221元由这5种组合的数量
2.组合里不包含100原,那就是321由前四种组合的数量

 

java实现：

 

public class Test2 {
  
    //1,5,10,50,100
    public static void main(String[] args){
      System.out.println(parseAllSeperationType(121, 5));
    }
    
    private static int parseAllSeperationType(int money, int typeNumber){

      if(typeNumber <= 0 || money < 0){
        return 0;
      }
      if(money == 0){
        return 1;
      }
      return parseAllSeperationType(money, typeNumber-1) + parseAllSeperationType(money - getMoneyByType(typeNumber), typeNumber);
    }

    private static int getMoneyByType(int typeNumber) {
      int money = 0;
      switch(typeNumber){
        case 5 : money = 100;
        break;
        case 4 : money = 50;
        break;
        case 3 : money = 10;
        break;
        case 2 : money = 5;
        break;
        case 1 : money = 1;
        break;
        default: money =0;
      }
      return money;
    }
}

 

如果再要求打印出所有的组合情况的话，稍作改动，java代码实现：

 

public class Test1 {
  
  private static int totals =0;
  
  public static void main(String[] args) {
    components(121, 100, "");
    System.out.println("total kinds number: " + totals);
  }

  //1, 5, 10, 50, 100
  private static void components(int money, int type_money, String printResult){
    if(type_money == 0 || money <= 0){
      //System.out.println(printResult);
      return;
    }
    int max_num = money/type_money;
    if(max_num > 0){
      for(int i=0; i <= max_num; i++){
        String printResultTem = printResult;
        if(i != 0){
          printResultTem += " " + type_money + ":" + i;
        }
        if(i*type_money == money){
          totals++;
          System.out.println(printResultTem);
          return;
        }
        components(money- i*type_money, getNextMoneyType(type_money), printResultTem );
      }
    }else{
      components(money, getNextMoneyType(type_money), printResult );
    }
  } 
  
  private static int getNextMoneyType(int typeNumber) {
    int money = 0;
    switch(typeNumber){
      case 100 : money = 50;
      break;
      case 50 : money = 10;
      break;
      case 10 : money = 5;
      break;
      case 5 : money = 1;
      break;
      case 1 : money = 0;
      break;
      default: money =0;
    }
    return money;
  }
}