OR-TOOL 背包算法

起因：最近公司要发票自动匹配，

比如财务输入10000W块，找到发票中能凑10000的。然后可以快速核销。

废话不多，

一 官方文档

https://developers.google.cn/optimization/pack/knapsack?hl=zh-cn

二 POM文件

        <!--google 算法包--><dependency><groupId>com.google.ortools</groupId><artifactId>ortools-java</artifactId><version>9.9.3963</version></dependency><!--google 算法包-->

三 代码

1 查询业务数据

说明：根据条件查询List<FsBill>,

由于发票金额的匹配，只有一个维度，所以设置values=amount,

然后调用knapsackSolver_invoice背包核心算法。

    @Overridepublic List<FsBill> solverBill(CheckingBill_Req req) {List<FsBill> fsBills = findCheckingBill(req);//背包算法只支持Long，所以amount*1000转换//由于不需要考虑价值因素，所以设置values=amount.这样可以匹配正好的金额。long[] values = fsBills.stream().mapToLong(x -> x.getTotalRateAmount().multiply(new BigDecimal(1000)).longValue()).toArray();//金额:小数*1000，作整数处理。long[][] amount = {values};//总金额*1000，作整数处理。long[] capacities = {req.getTotalAmount().multiply(new BigDecimal(1000)).longValue()};List<Integer> fsBillIndexs = knapsackSolver_invoice(values, amount, capacities);List<FsBill> solverBill = new ArrayList<>();if (!CollectionUtils.isEmpty(fsBillIndexs)) {for (Integer i : fsBillIndexs) {solverBill.add(fsBills.get(i));}}return solverBill;}

2 背包核心算法

说明：

values：代表物品价值(发票只有一个金额维度，所以values=weights)

weights：物品重量（此处可以传递发票金额amount）

返回的是List<Integer>数组下标，可以对应到List<FsBill>的对象。

@Overridepublic List<Integer> knapsackSolver_invoice(long[] values, long[][] weights, long[] capacities) {//加载OR-TOOL本地库Loader.loadNativeLibraries();//开始业务System.out.println("=========Begin : 匹配发票");KnapsackSolver solver = new KnapsackSolver(KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "test");solver.init(values, weights, capacities);final long computedValue = solver.solve();ArrayList<Integer> packedItems = new ArrayList<>();ArrayList<Long> packedWeights = new ArrayList<>();int totalWeight = 0;for (int i = 0; i < values.length; i++) {if (solver.bestSolutionContains(i)) {packedItems.add(i);packedWeights.add(weights[0][i]);totalWeight = (int) (totalWeight + weights[0][i]);}}//匹配金额System.out.println("Target amounts: " + capacities[0]);//总价值System.out.println("Total values: " + computedValue);//总重量System.out.println("Total amounts: " + totalWeight);//装载项的下标，可对应List<发票>的下标System.out.println("Packed items: " + packedItems);//装载项的重量System.out.println("Packed amounts: " + packedWeights);System.out.println("=========End : 匹配发票");//如果没有完全匹配金额，则清空packedItemsif (capacities[0] != totalWeight) {packedItems.clear();}return packedItems;}