求凑数算法

2022-03-25 09:28:46 +08:00
 dreasky

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

1991 次点击
所在节点    算法
11 条回复
noqwerty
2022-03-25 09:35:15 +08:00
01 背包问题
murmur
2022-03-25 09:39:01 +08:00
需求懂场景不懂，现在都是电子发票了，不需要节约纸质发票啊
afutureus
2022-03-25 09:40:31 +08:00
1 楼正解
shyrock
2022-03-25 09:55:14 +08:00
01 背包问题是解决一个背包最大化的算法吧。
能推广到 OP 这种要求 n 个背包最大化的场景吗？
ocean1477
2022-03-25 09:55:17 +08:00
dp[i] = Math.min(dp[i], dp[i - amounts[j]] + 1)
BBrother
2022-03-25 10:14:51 +08:00
对开票个数进行二分枚举，验证答案是否可行，就是二分答案的思路
Jooooooooo
2022-03-25 10:18:41 +08:00
确实是典型的背包问题, 搜一搜吧.
dayeye2006199
2022-03-25 10:24:46 +08:00
这个是个 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
2022-03-25 10:29:43 +08:00
https://v2ex.com/t/824934#reply29

同样遇到一个，试试 21 楼老哥给的 Google 工具。
dangyuluo
2022-03-25 13:44:19 +08:00
妈耶 leetcode 走入生活了
Renzo
2022-03-25 16:01:38 +08:00
背包问题,除了 ortools,还有一个 Optaplanner 可以试试.

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://tanronggui.xyz/t/842767

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX