我有ID(1001, 1002, 1003, 1004, 1005, 1006)的物品现在我有如下数据,每行有一个offerId。

offerId :{[Item_Id, Item_quantity_on_which_offer_Applied, Discount per quantity]}
1    :{[1001, 2, 21]}
4    :{[1002, 5, 5]}
6    :{[1003, 1, 25] [1004, 1, 25]}
5    :{[1004, 1, 20]}
3    :{[1005, 5, 17.5] [1002, 5, 17.5]}
2    :{[1005, 2, 18.33] [1001, 2, 26] [1006, 2, 21.67]}

解释当应用报价Idrespective quantities are (2, 5, 1, 1, 5, 2)时,我以每数量21卢比的折扣获得项目Id1数量,即在2数量上获得1002卢比的折扣。
目标我想得到最好的报价组合。例如,在上述情况下,最佳报价组合为:
报价:2(折扣=132(即(18.33+26+21.67)*2)
报价Id:3(注:由于报价Id 2中已包含3个21数量的项目1和3个1002数量的项目1005)(折扣=105(即(17.5+17.5)*3)
现在项目1002还有2数量,所以:
报价:4(适用于1005项目数量1002)(折扣=10(即5*2)
报价:6(折扣=(25+25)*1=50)
简而言之,报盘2、3、4、6将给我最好的报盘组合,其中报盘2适用于2数量的商品1002
提供3个数量的物品4和3个数量的物品2
以上是我希望根据数量计算最佳报价组合的结果。
到目前为止,我已经能够找到最好的报价组合,而不考虑数量。但现在我的要求是考虑项目的数量,然后找到最佳的报价组合。
如果有人能给我提供一个伪代码,那就真的很有帮助了。任何建议都非常感谢。
另外,我正在用Golang编写代码,但欢迎使用任何语言解决方案。
我希望我的问题是正确的。如果需要更多有关问题的信息,请在下面发表评论。
提前谢谢。

最佳答案

即使每种类型只有一个项目,而且每个报价都给出相同的总折扣(例如,$1),这也是NP难的,因为NP难问题Set Packing可以归结为:对于每个集合,对总折扣为$1的相同元素报价。因为所有的报价都提供相同的收益,所以这个问题的构造实例的最优解决方案是使用最多报价的,这个解决方案直接对应于原始集合包装问题的最优解决方案。
因此你的问题不可能有多项式时间的解决方案。

关于algorithm - 查找最佳报价组合的算法,该组合在给定的一组商品上提供最大的折扣,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/40652949/

10-11 21:32