定义输入
基本上你有一个产品列表pi，每个产品都有一个可能的优惠券代码列表[i]。List[i]包含所有j个可能适用于pi的优惠券。
产品数组: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 ...}
…等等upto 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，我们将无法申请优惠券。
S三个产品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 },
}
目标目标是简单地获得购买这些产品的最佳组合，以便将成本降低到最低。
只需要知道在这里应用的算法。搜索修剪是我现在想到的一件事，但我认为它不会像要求的那样高效。
我只能找到运行时间为0的朴素递归解(n(lI)的乘积)，即每个产品中优惠券数量的乘积顺序。
就像下面的例子一样，产品将是3*2*3*2 = 36
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