V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
dreasky
V2EX  ›  算法

求凑数算法

  •  
  •   dreasky · 2022-03-25 09:28:46 +08:00 · 1706 次点击
    这是一个创建于 734 天前的主题,其中的信息可能已经有所发展或是发生改变。

    现有大量商品销售数据 每条商品销售数据中包含一个"金额"字段 一张票据单号能开金额上限为 100000 总金额的发票 从大量商品金额中选择出总金额最接近但不超过 100000 的组合 使得开出的发票尽可能少 每月销售商品数据大约在百万数量级 递归遍历求组合性能低下 请问各位大神此类问题算是哪类算法 是否有比较好的解决思路

    第 1 条附言  ·  2022-03-25 11:17:44 +08:00
    感谢各位老哥,看了一圈还是 9 楼提供的装箱问题解决方案比较符合我的需求
    11 条回复    2022-03-25 16:01:38 +08:00
    noqwerty
        1
    noqwerty  
       2022-03-25 09:35:15 +08:00 via iPhone   ❤️ 1
    01 背包问题
    murmur
        2
    murmur  
       2022-03-25 09:39:01 +08:00   ❤️ 1
    需求懂场景不懂,现在都是电子发票了,不需要节约纸质发票啊
    afutureus
        3
    afutureus  
       2022-03-25 09:40:31 +08:00   ❤️ 1
    1 楼正解
    shyrock
        4
    shyrock  
       2022-03-25 09:55:14 +08:00   ❤️ 1
    01 背包问题是解决一个背包最大化的算法吧。
    能推广到 OP 这种要求 n 个背包最大化的场景吗?
    ocean1477
        5
    ocean1477  
       2022-03-25 09:55:17 +08:00   ❤️ 1
    dp[i] = Math.min(dp[i], dp[i - amounts[j]] + 1)
    BBrother
        6
    BBrother  
       2022-03-25 10:14:51 +08:00   ❤️ 1
    对开票个数进行二分枚举,验证答案是否可行,就是二分答案的思路
    Jooooooooo
        7
    Jooooooooo  
       2022-03-25 10:18:41 +08:00   ❤️ 1
    确实是典型的背包问题, 搜一搜吧.
    dayeye2006199
        8
    dayeye2006199  
       2022-03-25 10:24:46 +08:00 via Android   ❤️ 1
    这个是个 bin packing problem ,https://en.wikipedia.org/wiki/Bin_packing_problem

    Np hard ,没有线性时间精确解。但是有不少 heuristic, 例如 first fit https://en.wikipedia.org/wiki/First-fit_bin_packing#:~:text=First%2Dfit%20(FF)%20is,is%20at%20most%20the%20capacity.

    具体就是对每一个商品,遍历发票列表,找到有剩余金额可以容纳该商品的发票。如果找不到就新开一张发票。如此知道所有商品都被分配给某张发票。

    复杂度 Nk ,其中,N 为商品数量,k 为发票数量级。

    这个算法可以被理论证明不会使用超过 1.7 * 最少的发票数量。但实际使用中效果很好,一般远好于这个上界。
    cyrbuzz
        9
    cyrbuzz  
       2022-03-25 10:29:43 +08:00   ❤️ 1
    https://v2ex.com/t/824934#reply29

    同样遇到一个,试试 21 楼老哥给的 Google 工具。
    dangyuluo
        10
    dangyuluo  
       2022-03-25 13:44:19 +08:00 via iPhone
    妈耶 leetcode 走入生活了
    Renzo
        11
    Renzo  
       2022-03-25 16:01:38 +08:00
    背包问题,除了 ortools,还有一个 Optaplanner 可以试试.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5305 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 40ms · UTC 09:25 · PVG 17:25 · LAX 02:25 · JFK 05:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.