起因:最近公司要发票自动匹配,
比如财务输入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背包核心算法。
@Override public 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>的对象。
@Override public 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 : 匹配发票"); //如果没有完全匹配金额,则清空packedItems if (capacities[0] != totalWeight) { packedItems.clear(); } return packedItems; }
标签:背包,TOOL,List,System,long,算法,values,println,out From: https://www.cnblogs.com/hanjun0612/p/18130659