算法-最优解问题找零钱

问题

问题描述

给定 n 种不同面值的硬币，有一个总金额 k，计算出最少需要几枚硬币凑出这个金额k ？每种硬币的个数不限。如果没有任何一种硬币组合能组成总金额时，返回 -1。

示例：

输入：c[0]=1, c[1]=2, c[2]=5, k=12

输出：3 

解释：12 = 5 + 5 + 2

动态规划思路

初始化状态：由于动态规划是根据已经计算好的子问题推广到更大问题上去的，因此我们需要一个“原点”作为计算的开端；
状态：找出子问题与原问题之间会发生变化的变量，这个变量就是状态转移方程中的参数；
决策：改变状态，让状态不断逼近初始化状态的操作。这个决策，就是状态转移方程状态转移的方向。

分析

最少硬币数，显然也是一个求最值的问题。

可以从 0-k 求出每种面额下的最少硬币数，直到求出 k。

按动态规划思路来：

初始化状态

总额为0对应的硬币数也是0，总额>0 的 i 对应的硬币数最多就是 i + 1 （最小面值为1，所以最大就是 i，取一个不可能的最大值 i + 1 枚硬币）
状态参数

动态的总额 + 硬币数。寻找子问题发生变化的量。
决策

总额对应的最少硬币数 = min(x, (总额-该硬币面值) + 1) 。让状态不断逼近初始化状态的操作。
备忘录

dp[i] – i 表示总额，值就是硬币数

代码

动态规划

public class Coin {
    public static void main(String[] args) {
        // 硬币面值
        int[] values = {1, 2, 5};
        // 总值
        int total = 12;

        int minCounts = getMinCounts(total, values);

        System.out.println(minCounts);

    }

    static int getMinCounts(int k, int[] values) {
        // 创建备忘录 表示该总值 i 下的硬币最少个数
        int[] memo = new int[k + 1];
        // 初始化状态
        memo[0] = 0;
        // 初始化 memo[>0] k+1 表示最大硬币个数+1
        for (int i = 1; i < k + 1; i++) {
            memo[i] = k + 1;
        }

        for (int i = 1; i < k + 1; i++) {
            for (int coin : values) {
                if (i - coin < 0) {
                    continue;
                }
                // 做出决策
                // i - 当前coin
                memo[i] = Math.min(memo[i], memo[i - coin] + 1);
            }
        }

        return memo[k] == k + 1 ? -1 : memo[k];
    }

}

组合思路

套用组合的回溯算法：

public class Zuhe {
    private List<Integer> result = new ArrayList<>();

    private int target;
    private int min = Integer.MAX_VALUE;

    private List<Integer> selectors;

    public Zuhe(int target, List<Integer> selectors) {
        this.target = target;
        this.selectors = selectors;
    }

    public List<Integer> getResult() {
        return this.result;
    }

    public static void main(String[] args) {
        Zuhe zuhe = new Zuhe(12, Lists.newArrayList(1, 2, 5));
        zuhe.zuhe(new ArrayList<>(), 0);

        System.out.println(zuhe.getResult());
    }

    public void zuhe(List<Integer> track, int start) {
        int sumValue = track.stream().mapToInt(e -> e).sum();

        // 可复选的组合，一定要有return的条件【只有return才能回溯，不会无限制递归】
        if (sumValue > target) {
            return;
        }

        // 到目标值 收集track路径上的节点
        if (sumValue == target) {
            // 取数量小的
            if (track.size() < min) {
                min = track.size();
                result = new ArrayList<>(track);
            }
            return;
        }

        for (int i = start; i < selectors.size(); i++) {
            track.add(selectors.get(i));

            // 递归是向下一层多叉树的遍历，上述的return就是回溯
            // i 是可复选
            zuhe(track, i);

            track.remove(track.size() - 1);
        }
    }
}

算法