首页 > 编程语言 >OR-TOOL 背包算法

OR-TOOL 背包算法

时间:2024-04-12 10:49:10浏览次数:27  
标签:背包 TOOL List System long 算法 values println out

起因:最近公司要发票自动匹配,

比如财务输入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

相关文章

  • 补充:基于项目的协同过滤推荐算法(Item-Based Collaborative Filtering Recommendation
    前言继续上篇博客,继续读论文。想看上篇论文的同学可以点击这里相关工作Inthissectionwebrieflypresentsomeoftheresearchliteraturerelatedtocollaborativefiltering,recommendersystems,dataminingandpersonalization.在本节中,我们简要介绍了一些与协同......
  • 传统Item-Based协同过滤推荐算法改进
    前言今天要读的论文为一篇于2009年10月15日发表在《计算机研究与发展》的一篇会议论文,论文针对只根据相似性无法找到准确可靠的最近邻这个问题,提出了结合项目近部等级与相似性求取最近邻的新方法;此外针对系统中新加入的项目,因为其上评分信息的匾乏,求得的最近邻往往是不准确的,为此......
  • Top-N推荐算法 Top-N recommendation Algorithms
    引言推荐算法是计算机专业中的一种算法,通过一些计算,能够推测用户喜欢的东西,在互联网环境中应用比较广泛。Top-N算法在生活中非常常见,比如学术论文推荐论文、音乐软件推荐歌曲等。今天看到一篇名叫"ARevisitingStudyofAppropriateOfflineEvaluationforTop-NRecommendati......
  • 读论文-基于Python的协同过滤算法的研究与应用实现
    前言今天读的论文为一篇名为《基于Python的协同过滤算法的研究与应用实现》的论文,文章是在2019年9月发表于《电脑知识与技术》的一篇期刊论文。摘要随着科学技术的快速发展和知识产权的日益重要,大多数用户会选择在播放平台上看电影。例如腾讯视频、爱奇艺等,用户迫切需要一个合......
  • 读论文-基于自注意力机制和迁移学习的跨领域推荐算法
    前言今日要读的文章为一篇2022年4月2日发表于《计算机科学》的期刊文章;文章发现了传统的单领域推荐算法的问题:传统的单领域推荐算法受限于用户和项目的稀疏关系,存在用户/项目冷启动的问题,并且,其仅以用户对项目评分进行建模,忽略了评论文本中所蕴含的信息。基于此,文章提出了一种基......
  • 基于矩阵分解的协同过滤算法
    引言随着互联网、大数据等新技术的迅速发展,人们的生活变得更加便捷,但同时也导致网络数据爆炸式增长。为了快速帮助用户找到感兴趣的内容,越来越多的研究者致力于推荐算法的研究,以提高推荐质量,向用户推荐更符合其喜好的内容。然而,目前的推荐算法仍存在数据稀疏性、隐私保护和冷启动......
  • 基于注意力机制与改进TF-IDF的推荐算法
    前言本篇文章是2020年8月发表于《计算机工程》的一篇期刊论文,文章名称《基于注意力机制与改进TF-IDF的推荐算法》。文章针对传统推荐系统主要依赖用户对物品的评分数据而无法学习到用户和项目的深层次特征的问题,提出基于注意力机制与改进TF-IDF的推荐算法(AMITI)。将双层注意力......
  • 基于内容的电影推荐算法研究
    引言今天读的文章为一篇名为《基于内容的电影推荐算法研究》的文章,文章提出了一种基于内容的电影推荐算法,通过分析电影特征和用户兴趣,实现更精准的电影推荐。文章中使用到了TF-IDF向量化方法,将电影类型和导演信息转化为特征向量,然后使用余弦相似度来衡量电影之间的相关性,接下来......
  • 深入理解MD5算法:原理、应用与安全
    第一章:引言导言在当今数字化时代,数据安全和完整性变得至关重要。消息摘要算法是一种用于验证数据完整性和安全性的重要工具。在众多消息摘要算法中,MD5(MessageDigestAlgorithm5)因其快速、广泛应用和相对较高的安全性而备受关注。本书将深入探讨MD5算法的原理、应用和安全性,帮......
  • 超详细!详解一道高频算法题:数组中的第 K 个最大元素
    超详细!详解一道高频算法题:数组中的第K个最大元素今天分享的题目来源于LeetCode第215号问题,是面试中的高频考题。题目描述在未排序的数组中找到第k个最大的元素。请注意,你需要找的是数组排序后的第k个最大的元素,而不是第k个不同的元素。......