我有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]}
解释当应用报价Id
respective 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/