可叠加的优惠券最佳组合算法（Java）

一：前提知识

背景：给出一组优惠券，并给出优惠券叠加关系，优惠券权重

业务规则：某个类型的券存在最多限制

需求：求出优惠券在业务规则下最优组合（权重最大的组合）

名词规定：

• 图的团
• =图的集
• =图的完全子图

二：业务问题转为数学问题

当存在一组优惠券时，得到最优优惠券组合。首先将业务数据抽离为算法数据可得到如下图

其中 0-5编号代表优惠券编码，优惠券之间连线代表两者是可以共同使用的。

从数据结构上考虑，可以得知：这是一个无向有环图，问题不难转化为：求出有向无环图的所有子图。

从此图来看：

​ 所有完全子图包括：[[0,1,2],[3,4,5]]

​ 点对点情况：[[0,1],[0,2] ,[0,3] ,[5,2] ,[3,5] ,[1,2] ,[1,4] ,[3,4] ,[5,4]]

​ 单点情况：[0,1,2,3,4,5]

由于点对点和所有完全子图有重复对数据进行剪枝操作

剪枝后：

​ 所有完全子图包括：[[0,1,2],[3,4,5]]

​ 点对点情况：[ [0,3] ,[5,2] , [1,4]]

只需要求出所有子图的权重即可

综上所述，分为两步：

1. 找到图的所有完全子图
2. 权重最大的那一组作为最佳搭配

三：求图的完全子图（团、集）

总体思想：深度遍历这个图

计数方案：

四：数学问题再转为业务问题

业务代码如下：

• 数据结构实体
• 算法类
• 测试类

4.1：数据结构实体

package xyz.fudongyang.demo3;

import java.util.Objects;
import java.util.Set;

/**
 * @author: vfudongyang
 * @createTime: 2022年03月16日 18:08:00
 * @Description: 图节点通用结构体
 */

public class GraphStruct implements Comparable<GraphStruct> {

    /**
     * 业务字段：优惠券id
     */
    private Long couponId;

    /**
     * 业务字段：权重
     */
    private Double weight;

    /**
     * 业务字段：后序所有权重和(客户端不需要提供)
     */
    private int afterWeightSum = 0;

    /**
     * 业务字段：优惠券类型：PC EC
     *
     * @see CouponTypeEnum
     */
    private String type;

    /**
     * 图字段：下标
     */
    private transient Integer index;

    /**
     * 图字段：1 代表图节点被选中 0 代表图节点未被选中
     */
    private transient int isSelect = 0;

    /**
     * 图映射关系
     */
    private Set<GraphStruct> mappingLists;

    public GraphStruct(Long couponId, Double weight, Integer index) {
        this(couponId, weight, index, null);
    }

    public GraphStruct(Long couponId, Double weight, Integer index, String type) {
        this.couponId = couponId;
        this.weight = weight;
        this.index = index;
        this.type = type;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        GraphStruct that = (GraphStruct) o;
        return index.equals(that.index);
    }

    @Override
    public int hashCode() {
        return Objects.hash(index);
    }

    @Override
    public int compareTo(GraphStruct o) {
        return this.getIndex() - o.getIndex();
    }

    public Long getCouponId() {
        return couponId;
    }

    public void setCouponId(Long couponId) {
        this.couponId = couponId;
    }

    public Double getWeight() {
        return weight;
    }

    public void setWeight(Double weight) {
        this.weight = weight;
    }

    public int getAfterWeightSum() {
        return afterWeightSum;
    }

    public void setAfterWeightSum(int afterWeightSum) {
        this.afterWeightSum = afterWeightSum;
    }

    public String getType() {
        return type;
    }

    public void setType(String type) {
        this.type = type;
    }

    public Integer getIndex() {
        return index;
    }

    public void setIndex(Integer index) {
        this.index = index;
    }

    public int getIsSelect() {
        return isSelect;
    }

    public void setIsSelect(int isSelect) {
        this.isSelect = isSelect;
    }

    public Set<GraphStruct> getMappingLists() {
        return mappingLists;
    }

    public void setMappingLists(Set<GraphStruct> mappingLists) {
        this.mappingLists = mappingLists;
    }
}

4.2: 算法处理类

package xyz.fudongyang.demo3;

import org.springframework.lang.Nullable;

import java.util.*;

/**
 * @author: vfudongyang
 * @createTime: 2022年03月17日 14:30:00
 * @Description:
 */
public class GraphUtil {

    @Deprecated
    static int exc_sum = 0;

    // 选中图节点标志
    private final static int SELECTED = 1;

    // 未选中图节点标志
    private final static int UN_SELECT = 0;

    private final static String EC = "EC";

    private final static String PC = "PC";

    public static Set<GraphStruct> bestCombination(List<GraphStruct> metaData) {
        return bestCombination(metaData, false, null);
    }

    /**
     * 优惠券选择状态
     *
     * @param metaData     源数据信息
     * @param selectedList 已选数据
     * @param notOptionals 不可选数据
     * @param optionals    可选数据
     */
    public static void selectStatus(Map<Integer, GraphStruct> metaData, Set<GraphStruct> selectedList, Set<GraphStruct> notOptionals, Set<GraphStruct> optionals) {
        // 存放所有数据
        Map<Integer, Integer> dataMap = new HashMap<>();
        int selectedSize = selectedList.size();

        // EC PC 业务规则判断 PC 最多三个 EC 最多两个
        boolean banPC = isBan(selectedList, CouponTypeEnum.PC.getCode(), 3);

        boolean banEC = isBan(selectedList, CouponTypeEnum.EC.getCode(), 2);

        if (isEmpty(selectedList)) {
            optionals.addAll(metaData.values());
        } else {
            selectedList.forEach(e -> {
                // 存放元素本身
                addElement(dataMap, e.getIndex());

                // 存放元素关系网
                Set<GraphStruct> mappingLists = e.getMappingLists();
                if (!mappingLists.isEmpty()) {
                    mappingLists.forEach(g -> addElement(dataMap, g.getIndex()));
                }
            });
        }

        // 如果是可选状态 则元素需要两两需要连接 则需要判断元素的完全子图即可
        for (Map.Entry<Integer, Integer> entry : dataMap.entrySet()) {
            GraphStruct graphStruct = metaData.get(entry.getKey());

            if (selectedList.contains(graphStruct)) {
                continue;
            }

            if ((banEC && isEC(graphStruct)) || (banPC && isPC(graphStruct))) {
                notOptionals.add(graphStruct);
                continue;
            }

            if (selectedSize == entry.getValue() && !selectedList.contains(graphStruct)) {
                optionals.add(graphStruct);
            } else {
                notOptionals.add(graphStruct);
            }
        }
    }

    /**
     * 最佳优惠券组合
     *
     * @param metaData     源数据信息
     * @param dynamic      是否是动态选择
     * @param selectedList 已选数据
     * @return Set<GraphStruct> 优惠券最佳组合
     */
    public static Set<GraphStruct> bestCombination(List<GraphStruct> metaData, boolean dynamic,
                                                   List<GraphStruct> selectedList) {
        // 存放最佳组合的数据
        Set<GraphStruct> ans = new HashSet<>();

        int size = metaData.size();

        // 存放图数据结构
        int[][] maps = new int[size + 1][size + 1];

        // 存放下标对应的业务数据
        GraphStruct[] book = new GraphStruct[size + 1];

        // 处理前置数据----剪枝用
        preData(metaData, dynamic, selectedList);

        // 构件图
        buildGraph(metaData, maps, book);

        // 解析图
        dfs(1, Integer.MIN_VALUE, size, book, maps, ans, dynamic, selectedList);

        System.out.println("exc_sum = " + exc_sum);

        return ans;
    }

    private static void addElement(Map<Integer, Integer> dataMap, Integer index) {
        if (dataMap.containsKey(index)) {
            dataMap.put(index, dataMap.get(index) + 1);
        } else {
            dataMap.put(index, 1);
        }
    }

    private static boolean isEC(GraphStruct graphStruct) {
        return CouponTypeEnum.EC.getCode().equalsIgnoreCase(graphStruct.getType());
    }

    private static boolean isPC(GraphStruct graphStruct) {
        return CouponTypeEnum.PC.getCode().equalsIgnoreCase(graphStruct.getType());
    }

    private static boolean isBan(Set<GraphStruct> selectedList, String opt, int maxNum) {
        int sum = 0;
        for (GraphStruct graphStruct : selectedList) {
            if (opt.equalsIgnoreCase(graphStruct.getType())) {
                if (++sum >= maxNum) {
                    return true;
                }
            }
        }
        return false;
    }

    private static void preData(List<GraphStruct> metaData) {
        preData(metaData, false, null);
    }

    private static void preData(List<GraphStruct> metaData, boolean dynamic,
                                List<GraphStruct> selectedList) {
        // 计算每个节点 后续权重和 用于剪枝
        setAfterWeightSum(metaData);

        // 升序已选择的优惠券，得到数组第一个就是最小的下标
        if (dynamic && !isEmpty(selectedList)) {
            Collections.sort(selectedList);
        }
    }

    private static void setAfterWeightSum(List<GraphStruct> metaData) {
        Collections.sort(metaData);
        int sum = 0;
        ListIterator<GraphStruct> graphIterator = metaData.listIterator(metaData.size());
        while (graphIterator.hasPrevious()) {
            GraphStruct previous = graphIterator.previous();
            previous.setAfterWeightSum(sum);
            sum += previous.getWeight();
        }
    }

    private static void buildGraph(List<GraphStruct> metaData, int[][] maps,
                                   GraphStruct[] book) {

        for (GraphStruct graphStruct : metaData) {

            // 构建下标对应业务数据
            Integer index = graphStruct.getIndex();
            book[index] = graphStruct;

            // 构建图
            Set<GraphStruct> mappingLists = graphStruct.getMappingLists();
            if (!isEmpty(mappingLists)) {
                mappingLists.forEach(e -> maps[index][e.getIndex()] = SELECTED);
            }
        }
    }

    private static Integer dfs(int idx, Integer maxWeight, int size, GraphStruct[] book,
                               int[][] maps, Set<GraphStruct> ans) {
        return dfs(idx, maxWeight, size, book, maps, ans, false, null);
    }

    /**
     * @param idx          第idx个点 从 下标1开始
     * @param maxWeight    全中国
     * @param size         数据集合大小
     * @param book         元数据集合
     * @param maps         数据间图形数据结构
     * @param ans          最佳组合优惠券结果集合
     * @param dynamic      是否是动态选择
     * @param selectedList 已选择的优惠券
     * @return Integer     当前权重
     */
    private static Integer dfs(int idx, Integer maxWeight, int size, GraphStruct[] book,
                               int[][] maps, Set<GraphStruct> ans, boolean dynamic,
                               List<GraphStruct> selectedList) {
        exc_sum++;

        if (idx == size + 1) {
            // 如果不包含已经选择的优惠券 则可以废弃该结果集
            if (dynamic && !isEmpty(selectedList)
                    && !resultContainsSelect(book, selectedList)) {
                return maxWeight;
            }

            int bookSumWeight = getBookSumWeight(book);
            if (maxWeight < bookSumWeight) {
                // 获取到选中的数据存放到结果集种
                ans.clear();
                saveResult(book, ans);
            }
            return Math.max(maxWeight, bookSumWeight);
        }

        for (int i = 0; i < 2; i++) {//二叉树

            if (i == 0) {
                // 不选节点，构建二叉树
                // idx后面所有的权重加起来都没这个大的话 就没必要执行了(剪枝1)
                if (cutAfterData(maxWeight, idx, book)) {
                    maxWeight = dfs(idx + 1, maxWeight, size, book, maps, ans, dynamic, selectedList);
                }

            } else {
                // 选中节点，构建二叉树
                // 如果不满足完全子图，没必要构建（剪枝2）
                if (check(idx, book, maps)) {

                    book[idx].setIsSelect(SELECTED);

                    // 如果不满足PC EC业务规则 则不允许执行（业务规则）
                    if (ruleCheck(book)) {
                        maxWeight = dfs(idx + 1, maxWeight, size, book, maps, ans, dynamic, selectedList);
                    }

                    book[idx].setIsSelect(UN_SELECT);
                }
            }
        }
        return maxWeight;
    }

    private static boolean check(int idx, GraphStruct[] book, int[][] maps) {

        for (int i = 1; i < idx; i++) {
            // 如果他们不是完全子图 就可以过滤掉了 前期我们已经选择了一些节点
            if (book[i].getIsSelect() == SELECTED && maps[i][idx] != SELECTED) {
                return false;
            }
        }

        return true;

    }

    private static int getBookSumWeight(GraphStruct[] book) {
        int sum = 0;
        for (GraphStruct graphStruct : book) {
            if (graphStruct != null && graphStruct.getIsSelect() == SELECTED) {
                sum += graphStruct.getWeight();
            }
        }
        return sum;
    }

    private static void saveResult(GraphStruct[] book, Set<GraphStruct> ans) {
        for (GraphStruct graphStruct : book) {
            if (graphStruct != null && graphStruct.getIsSelect() == SELECTED) {
                ans.add(graphStruct);
            }
        }
    }

    private static boolean ruleCheck(GraphStruct[] book) {
        int pcSum = 0;
        int ecSum = 0;
        for (GraphStruct graphStruct : book) {
            if (graphStruct == null) {
                continue;
            }
            if (pcSum > CouponTypeEnum.PC.getMaximum() || ecSum > CouponTypeEnum.EC.getMaximum()) {
                return false;
            }

            if (graphStruct.getIsSelect() == SELECTED) {
                if (CouponTypeEnum.PC.getCode().equalsIgnoreCase(graphStruct.getType())) {
                    pcSum++;
                }

                if (CouponTypeEnum.EC.getCode().equalsIgnoreCase(graphStruct.getType())) {
                    ecSum++;
                }
            }
        }
        return true;
    }

    private static boolean cutAfterData(int maxWeight, int idx, GraphStruct[] book) {
        int before = 0;
        int after = book[idx].getAfterWeightSum();
        for (int i = 0; i <= idx; i++) {
            if (book[i] != null && book[i].getIsSelect() == SELECTED) {
                before += book[i].getWeight();
            }
        }
        return maxWeight < before + after;
    }

    private static boolean resultContainsSelect(GraphStruct[] book,
                                                List<GraphStruct> selectedList) {
        for (GraphStruct graphStruct : selectedList) {
            if (book[graphStruct.getIndex()].getIsSelect() == UN_SELECT) {
                return false;
            }
        }

        return true;
    }

    public static boolean isEmpty(@Nullable Collection<?> collection) {
        return collection == null || collection.isEmpty();
    }


}

4.3: 测试类

package xyz.fudongyang.demo3;


import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author: vfudongyang
 * @createTime: 2022年03月17日 15:57:00
 * @Description:
 */
public class BestCombinationTest {
    public static void main(String[] args) {
        GraphStruct graphStructA = new GraphStruct(1L, 5D, 1, "EC");
        GraphStruct graphStructB = new GraphStruct(2L, 8D, 2, "EC");
        GraphStruct graphStructC = new GraphStruct(3L, 20D, 3, "EC");
        GraphStruct graphStructD = new GraphStruct(4L, 2D, 4, "EC");
        GraphStruct graphStructE = new GraphStruct(5L, 7D, 5, "EC");

        List<GraphStruct> reqList = new ArrayList<>();

        Set<GraphStruct> graphA = new HashSet<>();
        graphA.add(new GraphStruct(2L, 8D, 2, "EC"));
        graphA.add(new GraphStruct(3L, 20D, 3, "EC"));
        graphA.add(new GraphStruct(4L, 20D, 4, "EC"));
        graphA.add(new GraphStruct(5L, 7D, 5, "EC"));
        graphStructA.setMappingLists(graphA);
        reqList.add(graphStructA);

        Set<GraphStruct> graphB = new HashSet<>();
        graphB.add(new GraphStruct(1L, 5D, 1, "EC"));
        graphB.add(new GraphStruct(3L, 20D, 3, "EC"));
        graphB.add(new GraphStruct(5L, 7D, 5, "EC"));
        graphStructB.setMappingLists(graphB);
        reqList.add(graphStructB);

        Set<GraphStruct> graphC = new HashSet<>();
        graphC.add(new GraphStruct(1L, 5D, 1, "EC"));
        graphC.add(new GraphStruct(2L, 8D, 2, "EC"));
        graphC.add(new GraphStruct(4L, 20D, 4, "EC"));
        graphStructC.setMappingLists(graphC);
        reqList.add(graphStructC);

        Set<GraphStruct> graphD = new HashSet<>();
        graphD.add(new GraphStruct(1L, 5D, 1, "EC"));
        graphD.add(new GraphStruct(3L, 20D, 3, "EC"));
        graphD.add(new GraphStruct(5L, 7D, 5, "EC"));
        graphStructD.setMappingLists(graphD);
        reqList.add(graphStructD);

        Set<GraphStruct> graphE = new HashSet<>();
        graphE.add(new GraphStruct(1L, 5D, 1, "EC"));
        graphE.add(new GraphStruct(2L, 8D, 2, "EC"));
        graphE.add(new GraphStruct(4L, 20D, 4, "EC"));
        graphStructE.setMappingLists(graphE);
        reqList.add(graphStructE);

        Set<GraphStruct> graphStructs = GraphUtil.bestCombination(reqList);
        System.out.println("======最佳优惠券组合==========");
        graphStructs.forEach(e -> System.out.println(e.getCouponId()));

    }
}

4.4冗余设计其他类

package xyz.fudongyang.demo3;

/**
 * @author: vfudongyang
 * @createTime: 2022年03月18日 17:23:00
 * @Description:
 */
public enum CouponTypeEnum {

    PC("PC", "优惠券PC码标识", 3),

    EC("EC", "优惠券EC码标识", 2),
    ;

    private final String code;

    private final String desc;

    private final Integer maximum;

    CouponTypeEnum(String code) {
        this(code, "");
    }

    CouponTypeEnum(String code, String desc) {
        this(code, desc, null);
    }

    CouponTypeEnum(String code, String desc, Integer maximum) {
        this.code = code;
        this.desc = desc;
        this.maximum = maximum;
    }

    public String getCode() {
        return code;
    }

    public String getDesc() {
        return desc;
    }

    public Integer getMaximum() {
        return maximum;
    }

    public static CouponTypeEnum getByCode(String code) {
        for (CouponTypeEnum value : CouponTypeEnum.values()) {
            if (value.code.equalsIgnoreCase(code)) {
                return value;
            }
        }
        return null;
    }
}