本文共 3573 字，大约阅读时间需要 11 分钟。

RMB组合,有如下RMB 面额, 1,2,5,10,20,50,100,给定一个RMB总额,求组合方案。各纸币面额数没有限制。

import java.util.ArrayList;import java.util.List;import java.util.Scanner;/** * Title： * Description：递归 * 
 * RMB面额：1 2 5 10 20 50 100 * 给定一个总额，求组合方案，面额纸币数量不限制且无限 * * @author WZQ * @version 1.0.0 * @date 2021/3/26 */public class Money01 {
       // 面额    static int[] money = {
   1, 2, 5, 10, 20, 50, 100};    static List
    
     
      > result = new ArrayList<>();    public static void main(String[] args) {
           Scanner input = new Scanner(System.in);        int n = input.nextInt();        dfs(new ArrayList<>(), 0, n, 0);        // 打印结果        for (List
      
        list : result) {
               System.out.println(list);        }    }    /**     * 递归回溯     *     * @param lists   存放已选     * @param sum     总额     * @param current 当前额     */    public static void dfs(List
       
         lists, int k,  int sum, int current) {
           if (sum == current) {
               // 符合的结果，需要重新new            result.add(new ArrayList<>(lists));        }        if (sum <= current || k >= 7 || sum < current + money[k]) {
               return;        }        // 各种面值递归        for (int i = k; i < money.length; i++) {
               lists.add(money[i]);            dfs(lists, i, sum, current + money[i]);            // 回溯，删除最后一个            lists.remove(lists.size() - 1);        }    }    /**     * 动态规划     * @param n 总额     */    public static void dy(int n) {
           // 纸币面额        int[] money = {
   1, 2, 5, 10, 20, 50, 100};        // 当前总额的组合数        int[] dp = new int[n + 1];        dp[0] = 1;        for (int i = 0; i < 7; ++i) {
               // 公式            for (int j = money[i]; j <= n; ++j) {
                   dp[j] = (dp[j] + dp[j - money[i]]);            }        }        System.out.println(dp[n]);    }}
       
      
     
    

问题进阶：RMB组合, 有如下RMB 面额, 1,2,5,10,20,50,100，给定各纸币面额数量和RMB总额，求组合方案，打印各方案的选择，这里不是计数，而且各面额纸质数量有限制，题目输入。

import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Scanner;/** * Title： * Description：递归回溯 * 
 * RMB面额：1 2 5 10 20 50 100 * 给定各面额纸质数和一个总额，求组合方案 * * @author WZQ * @version 1.0.0 * @date 2021/3/26 */public class Money02 {
       // 面额    static int[] money = {
   1, 2, 5, 10, 20, 50, 100};    // 统计面额纸币数    static Map
    
      maps = new HashMap<>();    static List
     
      
       > result = new ArrayList<>();    public static void main(String[] args) {
           Scanner input = new Scanner(System.in);        int n = input.nextInt();        // 输入每种面额纸币数        for (int i = 0; i < 7; i++) {
               int m = input.nextInt();            maps.put(money[i], maps.getOrDefault(money[i], 0) + m);        }        dfs(new ArrayList<>(), 0, n, 0);        // 打印结果        for (List
       
         list : result) {
               System.out.println(list);        }    }    /**     * 递归回溯     *     * @param lists   存放已选     * @param k 当前位置，后面比前大，保证顺序和唯一     * @param sum     总额     * @param current 当前额     */    public static void dfs(List
        
          lists, int k, int sum, int current) { if (sum == current) { // 符合的结果，需要重新new result.add(new ArrayList<>(lists)); } if (sum <= current || k >= 7 || sum < current + money[k]) { return; } // 各种面值递归，只能大于等于k for (int i = k; i < 7; i++) { if (maps.get(money[i]) >= 1){ // 使用该面额纸币 lists.add(money[i]); maps.put(money[i], maps.get(money[i]) - 1); dfs(lists, i , sum, current + money[i]); // 回溯 lists.remove(lists.size() - 1); maps.put(money[i], maps.get(money[i]) + 1); } } }}
        
       
      
     
    

转载地址：http://vviwi.baihongyu.com/