输入目标金额获取不同面额的组合算法[java实现]

如题，最近做项目的时候遇到这样一个需求，在此记录下，希望对大家有所帮助。目前只用了递归算法来实现，欢迎大家分享更好的算法。

具体业务场景如下：
商户有 100元、50元、20元、10元、5元、2元共6种面额的优惠券，假设每种面额库存有限；
用户A需要从商户购买指定额度的优惠券来使用，比如用户A需要从商户购买382元的优惠券来消费，请问：
1、商户已有的面额能否组合拼凑成用户想要的金额382元？
2、若能组合拼凑成用户想要的金额，如何按照大额优先的方式给到用户？（实际生活中商家找零钱场景，优先找大额度的RMB给客户）

代码如下：

/**
 * 组合算法：
 * 如给出200/100/50/25 等几种面额，在每种库存有限或者无限的情况下，输入金额300，按照优先取大额的规则获取组合：
 * 输入 300， 返回100*3
 * 输入425，返回：200 * 2 + 25 * 1
 */
public class Combination {

    /**
     * 获取组合
     * @param denominationsSortedByKeyDesc  面额，key: 面额值，value:库存，已按照key降序排序
     * @param target    需要组合的数值
     * @return  这里只返回一种组合方案（优先取大面额，取决于 denominations 的排序方式），key:面额，value:数量
     */
    public static Map<Double, Integer> getCombinationDenominationMaxFirst(NavigableMap<Double, Integer> denominationsSortedByKeyDesc, double target)
            throws IllegalArgumentException {
        if (denominationsSortedByKeyDesc == null || denominationsSortedByKeyDesc.size() == 0) {
            throw new IllegalArgumentException("Param denominations can not be null or empty.");
        }
        Map<Double, Integer> result = new HashMap<Double, Integer>();
        // 获取最大值
        double max = denominationsSortedByKeyDesc.firstKey();
        int inventory = denominationsSortedByKeyDesc.firstEntry().getValue();
        int times = (int) (target / max);
        // 可以直接由最大金额组成，无需往下判断
        if (target % max == 0 && times <= inventory) {
            result.put(max, times);
            return result;
        }
        // 只有一个面额的情况
        if (denominationsSortedByKeyDesc.size() == 1) {
            throw new IllegalArgumentException("target value have none combinations.");
        }
        double min = denominationsSortedByKeyDesc.lastKey();
        // 目标金额比最小面额还小，无法组合
        if (target < min) {
            throw new IllegalArgumentException("target value have none combinations.");
        }
        if (times > inventory) {
            times = inventory;
        }
        for (int i = times; i >= 0; i--) {
            if (i > 0) {
                result.put(max, i);
            }
            try {
                result.putAll(getCombinationDenominationMaxFirst(denominationsSortedByKeyDesc.subMap(max, false, min, true), target - i * max));
                return result;
            } catch (Exception e) {
                result.clear();
                continue;
            }
        }
        throw new IllegalArgumentException("target value have none combinations.");
    }

    public static void main(String[] args) {
        NavigableMap<Double, Integer> denominations = new TreeMap<Double, Integer>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                if (o2.doubleValue() > o1.doubleValue()) {
                    return 1;
                } else if (o2.doubleValue() == o1.doubleValue()) {
                    return 0;
                } else {
                    return -1;
                }
            }
        });
        denominations.put(10d, 3);
        denominations.put(3d, 3);
        denominations.put(1.5d, 3);
        denominations.put(5d, 3);

        System.out.println(getCombinationDenominationMaxFirst(denominations, 34.5));
    }

}

最后编辑于：2019.10.21 20:52:58