精打细算：OptaPlanner 如何帮助您找到最佳优惠券组合

2023-06-14
湖北
本文字数：1560 字
阅读完需：约 5 分钟

优惠券组合问题，它是一个组合优化问题，具体来说，给定一个订单金额和若干个优惠券，需要从这些优惠券中选择一些使用，使得总优惠金额最大，从而使得订单金额最小。

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

可以使用“动态规划算法”来解决这个问题。

动态规划算法

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];}

复制代码

OptaPlanner 算法

模型设计

EntityClass:：CouponItem

FactClass：OrderItem

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

约束设计

优惠券组合金额不能大于订单金额。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");}

复制代码

优惠券优惠金额最大。

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");}

复制代码

激励的方式也可以做到，但是感觉不够优雅。

知识点

forEach 和 forEachIncludingNullVars 的区别，因为 planningVariable 变量是允许为 null 的，所以为了尽可能的不为 null，所以需要惩罚，要使用 forEachIncludingNullVars

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/95cf5ff0bc8fad7d62f4f97bd】。

PeterOne

关注

认真生活，快乐工作 2020-06-17 加入

从业十年的老兵

发布

暂无评论

创作场景

精打细算：OptaPlanner 如何帮助您找到最佳优惠券组合

动态规划算法

OptaPlanner 算法

知识点

PeterOne

评论