优惠券组合问题是一个组合优化问题

目的是在给一个订单金额和若干个优惠券的情况下，从这些优惠券中选择一些使用，使得总优惠金额最大，从而使得订单金额最小。
具体来说，优惠券组合问题要求我们在所有可能的优惠券组合中，找到一组使得总优惠金额最大的优惠券，并将这些优惠券应用于订单中，以最小化订单金额。这是一个实际生活中经常遇到的问题，例如在购物时使用优惠券，或者在餐厅用餐时使用优惠券等。解决这个问题需要运用组合优化算法来进行计算和优化。

假设问题

例如，假设订单金额为100元，有三张优惠券，分别为20元、30元和50元，我们需要从这三张优惠券中选择一些使用，使得总优惠金额最大。在这个例子中，最优的方案是选择20元和50元的优惠券，使得总优惠金额为70元，订单金额为30元。

动态规划算法

可以使用动态规划算法来解决这个问题，下面是一个Java代码：

public int getMaxDiscount(int[] coupons, int orderAmount) {
    int n = coupons.length;
    int[][] f = new int[n + 1][orderAmount + 1];
    int[][] g = new int[n + 1][orderAmount + 1];

    // 初始化
    for (int j = 0; j <= orderAmount; j++) {
        f[0][j] = 0;
    }

    // 计算状态
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= orderAmount; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= coupons[i - 1] && f[i - 1][j - coupons[i - 1]] + coupons[i - 1] > f[i][j]) {
                f[i][j] = f[i - 1][j - coupons[i - 1]] + coupons[i - 1];
                g[i][j] = 1;
            }
        }
    }

    // 回溯方案
    List<Integer> selected = new ArrayList<>();
    int j = orderAmount;
    for (int i = n; i >= 1; i--) {
        if (g[i][j] == 1) {
            selected.add(coupons[i - 1]);
            j -= coupons[i - 1];
        }
    }

    // 返回最大优惠金额
    return f[n][orderAmount];
}

至于动态规划算法的学习可以看下这篇文章：# 背包理论基础01背包-1

Optaplanner实现

模型设计

EntityClass:：CouponItem

FactClass：OrderItem

PlanningVariable：OrderItem(nullAble=true) 不是每个优惠券都可以使用

约束设计

1. 优惠券组合金额不能大于订单金额。 – Hard

Constraint requiredCouponAmtTotal(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(CouponItem.class)

            .groupBy(CouponItem::getOrderItem, sum(CouponItem::getCouponAmount))
            .filter((orderItem, couponAmout) -> couponAmout > orderItem.getOrderItemAmount())
            .penalize(HardMediumSoftScore.ONE_HARD,
                    (orderItem, couponAmout) -> couponAmout - orderItem.getOrderItemAmount())
            .asConstraint("requiredCouponAmtTotal");
}

2. 优惠券优惠金额最大。

Constraint couponPenalize(ConstraintFactory constraintFactory) {
    return constraintFactory.forEachIncludingNullVars(CouponItem.class)
            .filter(cp -> cp.getOrderItem() == null)
            .penalize(HardMediumSoftScore.ONE_MEDIUM, CouponItem::getCouponFullReductionAmount)
            .asConstraint("couponPenalize");
}

注意： 这个约束使用Medium或者Soft级别，因为只有一个约束，这个约束使用forEachIncludingNullVars可以选择planningVariable变量，目的是为了未分配订单的优惠券惩罚其满减金额，这样算法会提高分数而分配订单。

或者激励分数方式

Constraint couponAmtMax(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(CouponItem.class)

            .groupBy(CouponItem::getOrderItem, sum(CouponItem::getCouponFullReductionAmount))
            .reward(HardMediumSoftScore.ONE_SOFT, ((orderItem, integer) -> integer))
            .asConstraint("couponAmtMax");
}

激励的方式也可以做到，但是感觉不够优雅，而且官方的很多例子上，没有找到使用reward的例子源码。

知识点

forEach和forEachIncludingNullVars的区别，因为planningVariable变量是允许为null的，所以为了尽可能的不为null，所以需要惩罚，要使用forEachIncludingNullVars查找出啦为null的实例，这样分数初始化就是以负数分数开始。

21:06:28.858 [main        ] INFO  Solving started: time spent (263), best score (0hard/0medium/-160soft), environment mode (REPRODUCIBLE), move thread count (NONE), random (JDK with seed 0).

这样就会给优惠券指定订单，当然你可以试试forEach会出现什么效果？？？

文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。

THE END