algorithm - 查找最佳报价组合的算法，该组合在给定的一组商品上提供最大的折扣

我有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/