algorithm - 找不到可以找到为产品列表应用优惠券代码的最佳方式的算法

Question

定义输入

所以基本上你有一个产品 p_i 列表，每个产品都有一个可能的优惠券代码列表 list[i]。 List[i] 包含所有 j 个可能适用于 p_i 的优惠券。

产品数组:p[i] = { p1, p2, p3, p4 ....}

产品对象:

p[i] = {
   price,
   coupons: list[i]
   // it contains reference to all the coupons applicable to this product
}

列表[1] = {c1, c2, c3, c5 ...}
列表[2] = {c1, c2 ...}
列表[3] = {c2, c4, c5 ...}
列表[4] = {c3, c4, c5 ...}
...依此类推，直到 list[i]

产品列表中的优惠券对象:

list[i][j] = {
    discount: Number, 
    // the amount which will be deducted from ith product if list[i][j] product is applied 
    
    name: String
    // the name of the product this basically tells,
    // that to which coupon in the pool of coupons does this coupon refer to.
}

所有优惠券池 = {c1, c2 ,c2 ,c4 ,c5 ,c6, c7....}
池中的优惠券对象:

c[j] = {
    minPriceToAvail: Number,
}

注意:

• 我们一次只能使用一张优惠券。

• 我们不必一次购买所有东西，我们可以多次购买。

• 如果我们要购买的所有适用此优惠券的产品总和小于 minPriceToAvail，我们将无法应用优惠券。
  例如，三个产品p1,p2,p3，价格分别为2000,1000,500，使用优惠券的最低价格为2000。
  此优惠券仅适用于p2和p3，因此我们无法使用它，
  因为所有有这张优惠券的产品加起来才1500

示例

p[i] = `{ shirt, laptop, book, mouse }`
// now every product have price and coupons list.

shirt = {
  price: 400,
  coupons: [ SALE10, DISC20, WELCOME ]
}
// each coupon here will have a discount amount and reference to pool of object 
// which here for simplicity let be the same as the name of the object


shirt.coupons.SALE10 = { discount: 100, name: SALE10 }

// this means that when this coupon will be applied,
// the price of the shirt will be deducted by 100

shirt.coupons.DISC20 = { discount: 20, name: DISC20 }
shirt.coupons.WELCOME = { discount: 0, name: WELCOME }


// similarly for every product

laptop = {
    price: 40000,
    coupons: [
        { discount: 10000, name: DISC10 },
        { discount: 15000, name: ELECTRO },
    ],
}
book = {
    price: 1000,
    coupons: [
        { discount: 30, name: LUCKY },
        { discount: 50, name: DISC10 },
        { discount: 400, name: BOOKS },
    ],
}

mouse = {
    price: 2000,
    coupons: [
        { discount: 200, name: LUCKY },
        { discount: 1000, name: WELCOME },
    ],
}

allCoupons = {
    SALE10: { minPriceTotal: 300 },
    DISC20: { minPriceTotal: 1000 },
    DISC10: { minPriceTotal: 500 },
    WELCOME: { minPriceTotal: 2500 },
    BOOKS: { minPriceTotal: 2000 },
    LUCKY: { minPriceTotal: 500 },
    ELECTRO: { minPriceTotal: 5000 },
}

目标

目标是简单地获得购买这些产品的最佳组合，从而将成本降至最低。
只需要知道这里应用的算法即可。搜索修剪是我现在想到的一件事，但我认为不会达到所需的效率。
我只能找到简单的递归解决方案，该解决方案将以 O( n(l_i) 的乘积 ) 运行，即按每个产品中优惠券数量的产品顺序。
就像下面的示例一样，产品将为 3*2*3*2 = 36

Answer 1

这是 MILP 公式

数据:

D_p_d: price discount for product p and discount d
T_d: min total price for discount d
P_p: price of product p
M: large enough number

变量:

x_p_d: 1 if product p bought with discount d otherwise 0
z_d: 1 if discount d used otherwise 0

型号:

min sum_p(P_p) - sum_p(sum_d(D_p_d*x_p_d))
subject to

    1. sum_d(x_p_d) <= 1, for all p (use max one discount per product)
    2. M*z_d >= sum_p(x_p_d), for all d (connect x and z)
    3. z_d <= sum_p(x_p_d), for all d (connect x and z)
    4. M(1-z_d) >= T_d - sum_p(P_p*x_p_d), for all d (discount can only be used if total price is at least minPriceTotal)

这可以实现，例如使用 PuLP，这是 MiniZinc 实现(其中 M 值已收紧):

int: nProducts = 4;
int: nDiscounts = 7;

set of int: PRODUCT = 1..nProducts;
set of int: DISCOUNT = 1..nDiscounts;
                     
array[DISCOUNT] of int: minPriceTotal = [300, 1000, 500, 2500, 2000, 500, 5000];

array[PRODUCT, DISCOUNT] of int: discount = [|
    100, 20, 0, 0, 0, 0, 0|
    0, 0, 10000, 0, 0, 0, 15000|
    0, 0, 50, 0, 400, 30, 0|
    0, 0, 0, 1000, 0, 200, 0|];
    
array[PRODUCT] of int: price = [400, 40000, 1000, 2000];

array[PRODUCT, DISCOUNT] of var 0..1: x;
array[DISCOUNT] of var 0..1: z;

% use max one discount per product
constraint forall(p in PRODUCT)
    (sum(d in DISCOUNT)(x[p, d]) <= 1);

% connect x and z
constraint forall(d in DISCOUNT)
    (nProducts*z[d] >= sum(p in PRODUCT)(x[p, d]) /\ 
     z[d] <= sum(p in PRODUCT)(x[p, d]));

% discount can only be used if total price is at least minPriceTotal
constraint forall(d in DISCOUNT)
    (max(minPriceTotal)*(1 - z[d]) >= minPriceTotal[d] - sum(p in PRODUCT)(price[p]*x[p, d]));
            
var int: obj = sum(price) - 
    sum(p in PRODUCT, d in DISCOUNT)(discount[p,d]*x[p,d]);

solve
minimize obj;

output ["obj=\(obj)\n"] ++
["z=\n"] ++ [show(z)] ++
["\nx=\n"] ++ [show2d(x)];

运行给出:

obj=27300
z=
[1, 0, 0, 1, 0, 0, 1]
x=
[| 1, 0, 0, 0, 0, 0, 0 |
   0, 0, 0, 0, 0, 0, 1 |
   0, 0, 0, 1, 0, 0, 0 |
   0, 0, 0, 1, 0, 0, 0 |]

解读:

• 使用首次折扣 (SALE10) 购买第一件产品。折扣=100
• 使用第七次折扣 (ELECTRO) 购买第二件产品。折扣=15000
• 使用第四个折扣购买第三个和第四个产品(欢迎)。折扣 = 0 + 1000