硬币找零的算法，使用递归，第一个为最少的找零数量

 
package test;
import java.util.Stack;
class Money {
  int fen;
  int number;
}
public class Temp {
  static Stack<Money> stack = new Stack<Money>();
  // 假设只有1角，5分，2分和1分。如果更多，请自行添加，记得金额从大到小排列
  static int[] nums = new int[] { 10, 5, 2, 1 }; 
  public static void fen(int target, int sum, int index) {
    for (int i = index; i < nums.length; i++) {
      int num = nums[i];
      if (num > target) { // 如果面值超过找零的数值，则忽略
        continue;
      }
      Money m = new Money();
      m.fen = num;
      stack.push(m);
      while (sum + num <= target) {
        m.number++;
        if (sum + num == target) {
          showResult();
        }
        sum += num;
      }
      fen(target, sum, i + 1);
      stack.pop();
      sum -= m.fen * m.number;
    }
  }
  private static void showResult() {
    for (Money m : stack) {
      if (m.number > 0) {
        System.out.print(m.fen + ":" + m.number + " ");
      }
    }
    System.out.println();
  }
  public static void main(String[] input) throws Exception {
    fen(17, 0, 0); // 测试找1角7分
  }
}

运行结果
10:1 5:1 2:1 
10:1 5:1 1:2 
10:1 2:3 1:1 
10:1 1:7 
5:3 2:1 
5:3 1:2 
2:8 1:1 
1:17