我需要有关棘手问题的专家建议。
该方案是:
产品由唯一的ProductID标识并具有销售价格。非常经典的场景。
该产品还可以享受一种或多种折扣。
折扣可以是不同的类型。折扣的一个示例是:
订单项只能获得一个折扣,因此,一旦对某个订单项进行了折扣,就无法再享受其他折扣。
测试案例数据:
折扣-A :购买两个或更多,即可获得以下任意一种产品的20%的折扣
Discount-B :购买产品并获得以下产品50%的折扣
测试方案1:
购物篮:包含具有以下内容的订单项:
计算#1 :
计算#2 :
这意味着 Discount-A 和 Discount-B 的组合将为客户提供最佳折扣。
测试方案2:
购物篮:包含具有以下内容的订单项:
计算#1 :
计算#2 :
这意味着应用折扣-将为客户提供最佳折扣。
为了计算给定购物篮的最佳折扣,实际上必须评估产品的所有组合以及这些产品的可用折扣。
通常,购物篮中有30-40个订单项,每个项目都有0-3的折扣。
基本上,我一直坚持寻找一种有效的方法来执行此计算。
现在,我使用折扣的算法类似于:
但这还远远不够,因为它没有尝试订单项/折扣的不同组合。
我一直在寻找可以解决此类问题的标准化算法,但到目前为止没有任何运气。
希望能从你那听到答复 :)
最佳答案
假如说:
然后该问题成为一个称为assignment的问题,可以使用Hungarian algorithm在O(n ^ 3)中最佳解决。
您将需要计算一个矩阵M [a,b],其中包含在乘积b上使用折扣a时节省的钱。 (如果没有折扣,则将节省的金额设置为0。)
匈牙利算法将计算为节省最多金钱的产品分配折扣的方式。
如果折扣和产品的数量不同,则添加虚拟折扣(零储蓄)或虚拟产品(再次零储蓄),直到折扣数量与产品数量匹配为止。