查找最佳报价组合的算法，该组合在给定的一组商品上提供最大的折扣 [英] Algorithm to find best offer combination that gives maximum discount on a given set Of Items

问题描述

我有ID为（1001、1002、1003、1004、1005、1006）的项目。 的数量分别是（2、5、1、1、1、5、2）：现在我得到如下数据。每行都有一个offerId。

I have items with ID (1001, 1002, 1003, 1004, 1005, 1006). There respective quantities are (2, 5, 1, 1, 5, 2): Now I have data like following.There is an offerId for each row.

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 1 后，我在21 rs处获得了数量为 2 的项目ID 1002 。每个数量的折扣，即我得到 21 rs。 1 数量 1002 的折扣。

Explaination When offer Id 1 is applied, I get Item 2 quantities of Item Id 1002 at 21 rs. discount per quantity i.e. I am getting 21 rs. discount on 1 quantity of 1002.

目标，我想获得最好的报价组合。例如，在上述情况下，最佳报价组合将是：

Objective I want to get the best offer combination. For example in above case best offer combination will be:

OfferId：2（折扣= 132（即（18.33 + 26 + 21.67）* 2））

OfferId : 2 (discount = 132 (i.e. (18.33+26+21.67)*2))

OfferId：3（注释：用于3数量的商品 1005 和3数量的商品 1002 ，因为 2 数量为 1005 的商品已经在报价ID 2中）。 （折扣= 105（即（17.5 + 17.5）* 3））

OfferId : 3 (note: for 3 quantities of item 1005 and 3 quantities of item 1002 since 2 quantities of item 1005 is already in offer Id 2). (discount = 105(i.e. (17.5+17.5)*3))

现在项目 1002 的 2 剩余数量，因此：

Now item 1002 has 2 quantity remaining , so:

offerId：4（应用于 2 商品数量 1002 ）（折扣= 10（即5 * 2））

offerId : 4 (applied on 2 quantities of item 1002)(discount = 10(i.e 5*2))

offerId：6（折扣=（25 + 25）* 1 = 50）

offerId : 6 (discount = (25+25)*1 = 50)

因此，简而言之，offerids 2、3、4、6将为我提供报价<$$的最佳报价组合c $ c> 4 应用于 2 数量 1002 ，$ b $的项目b为3数量的商品 1005 和3数量的商品 1002 3 c $ c>。

So in a nutshell, offerids 2, 3 , 4 , 6 will give me best combination of offers where offer 4 is applied on 2 quantities of item 1002, offer 3 for 3 quantities of item 1005 and 3 quantities of item 1002.

以上是我希望根据数量计算最佳报价组合的结果。

Above is the result I desire to compute best offer combination depending on quantity.

到目前为止，我已经能够在不考虑数量的情况下找到最佳报价组合。但是现在我的要求是考虑物料的数量，然后找到最优惠的价格组合。

So far, I had been able to find best offer combination without considering quantity. But now my requirement is to consider quantities of Items and then find best offer combination.

如果有人可以向我提供伪代码，那将真的很有帮助。

It would be really helpful if anyone can provide me with a pseudocode. Any suggestions are greatly appreciated.

P.S。我正在用Golang编写代码，但是欢迎使用任何语言的解决方案。

P.S. I am writing my code in Golang but solutions in any language are welcomed.

我希望我正确地提出了问题。如果需要有关问题的更多信息，请在下面评论。
预先感谢。

I hope I framed my question correctly. Comment below if any more information regarding question is required. Thanks in advance.

推荐答案

即使每种类型只有一个商品，并且每个报价都提供相同的商品总折扣（例如$ 1），这是 NP困难，因为NP困难问题组合包装可以简化为：对于每个组合，以相同的折扣提供总价为$ 1的元素。由于所有报价都提供相同的收益，因此针对此构造的问题实例的最佳解决方案是使用报价的最大数量的解决方案，并且该解决方案直接对应于原始包装的最佳解决方案问题。

Even if there is only a single item of each type and every offer gives the same total discount (say, $1), this is NP-hard, since the NP-hard problem Set Packing can be reduced to it: for each set, make an offer for the same elements with total discount $1. Since all offers provide the same benefit, the optimal solution to this constructed instance of your problem is the one that uses the largest number of offers, and this solution corresponds directly to the optimal solution to the original Set Packing problem.

因此，没有希望为您的问题提供多项式时间解。

Thus there's no hope for a polynomial-time solution to your problem.

这篇关于查找最佳报价组合的算法，该组合在给定的一组商品上提供最大的折扣的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！