最优开票问题的算法
场景需求:
1、公司的单个客户有多达几百上千的订单,每个订单有订单号和订单金额
2、公司单张发票的限额是 10 万,即开票金额不能超过 10 万(同一客户多个订单可以开一张发票)
3、超过或等于 10 万的订单,单独开票不与其他订单整合
目标:
求订单开票组合的最优解(即以最少的发票消耗(发票张数)完成全部订单的开票)
各位大神,有没有好的算法,一起交流。同时,也希望有哪位大神能够基于集算器对算法进行实现,最好是能够形成 Excel add-ins 相对应的内嵌函数,提供更好的使用体验。
先抛出我的结题思路:
1、大于或等于 10 万的订单,每个订单一个开票组合
2、去掉大于或等于 10 万的订单后,计算剩余订单(小于 10 万订单)的最小订单金额 minAmt 和最大订单金额 maxAmt
3、从组合(排列组合中的组合)包含订单的个数的最小值开始处理(单订单组合)
4、其他所有订单 +minAmt>=10 万,则这些订单只能单个订单开票(即一个订单一张发票)
5、循环,去掉一张订单一张发票 的 对应订单
6、最小的 N 个订单求和,求和不大或等于 10 万的最小订单个数 minGN
7、求全部订单中 取 2 到 minGN 个订单的全部组合,并找出最接近 10 万的那个组合(改组合符合要求)
8、去掉符合要求的组合,循环 步骤 7 ,直到订单列表中 没有剩余的订单
该算法,比较啰嗦,算法复杂度很高。
请各位大神拍砖。
重要的事情:更快,复杂度更好的算法。
这个是背包问题的变种,貌似没有多项式复杂度的解法(细节记不清了),所以曾经用于公钥加密。
求最优解的方法基本上类似穷举。用递归后的代码倒不算很难写,但计算复杂度是指数级的,几百上千的规模就很大了,能不能算得快看运气。
可以去搜索一下背包问题现在有什么好一点解法。
要不然,如果规模太大,就别做最优解了,稍浪费一点也不要紧。
至于 Excel Add-ins 倒不是个事了。