Discount offers using Dynamic Programming?
Contributors: Bhavik Ambani, Vishvesh Oza
We at Myntra, give a lot of importance to our customers; we are highly customer-centric. One way we do this is by showcasing attractive prices for products, in particular, during sale days.
This EORS (End of Reason Sale), we decided to try out a relatively unique construct: buying a few items at MRP and getting a few more for free. This empowers the customer by providing the opportunity to obtain more products at prices cheaper than ever before.
Discount Construct
- A customer adds certain products to her cart.
- A choice is provided to her to add a few more items to her cart. This would result in a combo offer, which could provide her with cheaper prices overall.
- The discount construct would consist of the following :
* The combo offer would comprise of a Buy-Get(BG) construct.
If a few product(s) are bought, then few product(s) would be given for free. The products that are bought would be those which have the maximum un-discounted price in the set. This is the price the product is purchased at as part of the Buy-Get construct.
* The products could also be initially discounted.
If the product is heavily discounted initially, it would be available at a cheaper price than how much it would have been as part of the Buy-Get offer.
The cart calculates the best price from multiple combinations; whether to consider giving products at the original discounted price or whether to pick up the products with the Buy-Get offer. - The lowest price for the cart is calculated and that is shown to the customer.
Problem Description
The construct can be delineated as follows:
- Someone shopping on Myntra browses for products, selects a few items of interest and adds them to her bag. Many of these products are already on sale, having an existing discount applied onto them.
- The customer is now provided with an option of possibly buying one or more products at the original un-discounted price and getting a few more for free. For instance, an option could be that of buying 2 at the original un-discounted price and getting 3 more for free.
- A point to note is that the products had a pre-existing discount applied onto them.
- Should the products be bought as part of a Buy-Get offer or solely with their individual discounts? How many sets of Buy-Get are required? Which option would give the best total price to the customer?
- When a set of products is considered as part of a Buy-Get offer, the product(s) with maximum MRP is bought and the rest are offered for free.
- On choosing products, the algorithm computes the best combination of “buying-getting” for free or choosing products at their discounted price. The combination with the least total price is offered to the customer.
A programming problem?
Let the constructs be defined as follows,
MRP(Maximum Retail Price) : The actual price of the product
Disc. Price : The discounted price/best price that the product is inThe problem can be reduced to a simple scenario wherein each product can be defined by its MRP, which is the actual price of the product, and its discounted price.
Consider the following examples,
1. B1G1
╔═══════════╦═══════════════╦═══════════════╗
║ product ║ MRP ║ Disc. Price ║
╠═══════════╬═══════════════╬═══════════════╣
║ 1 ║ 1500 ║ 1050 ║
║ 2 ║ 1000 ║ 900 ║
║ 3 ║ 500 ║ 475 ║
║ 4 ║ 150 ║ 90 ║
║ 5 ║ 150 ║ 20 ║
╚═══════════╩═══════════════╩═══════════════╝ Here, 5 products are present in the bag which have a pre-existing discount applied onto them. An offer of Buy1Get1 is allowed on the bag. This would allow a single product to be obtained for free upon buying a product at a higher MRP.There could be many possible combinations. For example,
1. Combining products 1 and 2, buying 3,4,5 at disc. price. This would give a total of 1500+475+90+20 = 20852. Combining products 1 and 3,2 and 4, buying 5 at disc. price. This would give a total of 1500+1000+20 = 25203. Combining products 1 and 2, 3 and 4, buying 5 at disc. price. This would give a total of 1500 + 500 + 20 = 2020.The 3rd option is the best possible choice. So product 1 is bought at MRP and 2 is obtained for free. Product 2 is bought at MRP and 4 is obtained for free. The 5th product is bought at the discounted price.2. B1G1
╔═══════════╦═══════════════╦═══════════════╗
║ product ║ MRP ║ Disc. Price ║
╠═══════════╬═══════════════╬═══════════════╣
║ 1 ║ 1000 ║ 400 ║
║ 2 ║ 150 ║ 60 ║
║ 3 ║ 100 ║ 95 ║
╚═══════════╩═══════════════╩═══════════════╝Here, 3 products are present in the bag which have a pre-existing discount applied onto them. An offer of Buy1Get1 is allowed on the bag. This would allow a single product to be obtained for free upon buying a product at a higher MRP.There could be many possible combinations. For example,
1. Combining products 1 and 2, buying 3 at disc. price. This would give a total of 1000+95 = 10952. Buying 1,2,3 at disc. price. This would give a total of 400+60+95 = 5553. Buying 1 at disc. price and combining products 2,3. This would give a total of 400+150 = 550The 3rd option is the best possible choice. So product 1 is bought at the discounted price, product 2 is bought at MRP and product is 3 is obtained for free.3. B1G1
╔═══════════╦═══════════════╦═══════════════╗
║ product ║ MRP ║ Disc. Price ║
╠═══════════╬═══════════════╬═══════════════╣
║ 1 ║ 1000 ║ 400 ║
║ 2 ║ 150 ║ 60 ║
║ 3 ║ 100 ║ 40 ║
╚═══════════╩═══════════════╩═══════════════╝The best possible option is to buy all the products individually on their discounted price. This would give a total of 400+60+40 = 5004. B1G2
╔═══════════╦═══════════════╦═══════════════╗
║ product ║ MRP ║ Disc. Price ║
╠═══════════╬═══════════════╬═══════════════╣
║ 1 ║ 1000 ║ 900 ║
║ 2 ║ 150 ║ 60 ║
║ 3 ║ 100 ║ 60 ║
╚═══════════╩═══════════════╩═══════════════╝
Here, 2 products can be obtained for free when a product is bought at MRP. The best possible option here is to buy the first product at MRP and get the rest of them for free. The total would be 1000.5. B2G1
╔═══════════╦═══════════════╦═══════════════╗
║ product ║ MRP ║ Disc. Price ║
╠═══════════╬═══════════════╬═══════════════╣
║ 1 ║ 150 ║ 80 ║
║ 2 ║ 400 ║ 350 ║
║ 3 ║ 250 ║ 200 ║
║ 4 ║ 1000 ║ 950 ║
║ 5 ║ 100 ║ 100 ║
╚═══════════╩═══════════════╩═══════════════╝
Here two products can be bought at MRP and one can be obtained for free. The two products have to be those with maximum MRP in the set of three(2+1).
The best possible option is to combine products 2,3,4 and buying 1 and 5 at their discounted prices. Products 2 and 4 would be bought at MRP and 3 would be obtained for free. This would give a total of (1000+400)+80+100 = 1580
The examples explain the subtleties of the problem. Multiple combinations have to be considered to compute the best possible option for the customer.
This was the motive behind coming up with a recurrence formulation in order solve the problem both efficiently and methodically.
In production
An example of a bag with a BG offer is illustrated. A point to be noted here is that free products are given a final discount of 100% with the BG offer applied. Instead of giving products at a price of 0, the discounted amount is further equally divided amongst the rest of the products.
For example, if the final prices of two products are 100 and 0(free), the prices would be equally split as 50 and 50. Details regarding the split would be beyond the scope of this article.
Approach
Upon pondering over the problem, a few observations and patterns come to light.
- There could be multiple combinations. All the combinations have to be iterated over to obtain the solution. This would lead the solution into a dynamic programming based approach.
- Recurrence relations might be needed to problem the various cases. This would help in memoization to reduce time complexity.
- The list may needed to be sorted in some form, probably in descending order of MRP. This might help solve the case of choosing the maximum MRP product in case of a BG set. A greedy approach could be followed wherein first products could be taken at MRP and later on in the iteration process, products could be obtained for free. Sorting seems to help greatly here.
- To track what products should be bought as part of a BG set and what are bought at individual discounted prices, some sort of identification mapping could be present, to help track products after sorting.
Algorithm
The recurrence relations can be defined as follows.
Here b,g and i are iterators which are iterating over B,G and n.
For example, considering a bag which contains 5 products with a B1G2 offer, B=1, G=2 and n=5. b,g and i would iterate from 0 to 1, 0 to 2 and from 1 to 5 respectively.
- If b equals 0 and g equals 0: This would mean that either a new BG offer could be created or the current product’s discounted price could be considered and the remaining products can be checked over. This is basically a restart/start of the BG offer. If the BG offer is complete or not yet started(
b==0andg==0), then above two routes should be considered.
An edge case whereG=0has to be considered for completeness: If no product can be obtained for free, then the only option is to buy the product at its discounted price. - If g equals 0 and b does not equal to 0, this would mean that all the “get free” products have been used up from the end. As the list of products is sorted, all products from the end are picked up for free which leaves the remaining products at the beginning to be bought at MRP.
Values fromBcan now be deducted by picking 1 of theBproduct’s MRP or by picking up the product at the discounted price. Both the options have to compared. - If both of the above are not true, we are left with the final option that is the general case. Either a product can be obtained for free or the product can be picked up at its discounted price. Again, a greedy approach is utilized by picking up products for free from the end until g equals 0.
Finding which products belong to what construct : At every point of calculation of f, it is necessary to store the parent of the recurrence node in order to store the route that has led to this node. This would help in tracking the type of discount the product falls under.
Finally, the answer is just dp(n,B,G), which is the result till the nth product with a Buy B, Get G offer.
Code Snippets
The following are the Java code snippets for the solution.
// Initializationfinal int N = PriceList.size();
final double[][][] dp = new double[N+1][B+1][G+1];
PriceDetails[] prices = new PriceDetails[N+1];for (int i = 0; i < dp.length; i++)
for (int j = 0; j < dp[0].length; j++)
for (int k = 0; k < dp[0][0].length; k++)
dp[i][j][k] = Integer.MAX_VALUE;// assigned to any high valuedp[0][0][0] = 0;
dp[0][B][G] = 0;
A vector is initialized with a set of prices viz. the maximum retail price(mrp) and the discounted price(discp). The values of the recurrence can be memoized in a three-dimensional array, dp[maxN][maxB][maxG] where maxN,maxB and maxG are the respective maximum limits of N,B and G. N corresponds to the maximum number of elements in the bag. B represents the maximum number of “Buy Bs” that an offer could contain and G represents the maximum number of “Get Gs for free”.
// sort descendingArrays.sort(prices, 1, prices.length, new Comparator<PriceDetails>(){
@Override
public int compare(PriceDetails o1, PriceDetails o2) {
return new Double(o2.getMRP() - o1.getMRP()).intValue();
}
});
The prices are then sorted in descending order of the MRP.
// Compute values for dp(i,b,g) using the recurrence relations// To store parent values in order to backtrack to retrieve path
final BGValues[][][] parentValues = new BGValues[N+1][B+1][G+1];for(int i = 1; i <= N; i++) {
for(int b = 0; b <= B; b++) {
for(int g = 0; g <= G; g++) {
final int bVal, gVal;
if(b == 0 && g == 0) {
if(G>=1) {
if(dp[i-1][B][G]+prices[i].getDiscountedPrice() <
dp[i - 1][B][G -1]) {
dp[i][b][g] = dp[i-1][B][G]+prices[i].getDiscountedPrice();
bVal = B;
gVal = G;
}
else {
dp[i][b][g] = dp[i-1][B][G-1];
bVal = B;
gVal = G - 1;
}
}
else {
dp[i][b][g] = dp[i-1][B][G]+prices[i].getDiscountedPrice();
bVal = B;
gVal = G;
}
}
else {
if(g == 0) {
if(dp[i-1][b-1][g]+prices[i].getMRP() <
dp[i-1][b][g]+prices[i].getDiscountedPrice()) {
dp[i][b][g] = dp[i-1][b-1][g] + prices[i].getMRP();
bVal = b - 1;
gVal = g;
}
else {
dp[i][b][g]= dp[i-1][b][g] + prices[i].getDiscountedPrice();
bVal = b;
gVal = g;
}
}
else {
if(dp[i-1][b][g-1] <
dp[i-1][b][g] +prices[i].getDiscountedPrice()) {
dp[i][b][g] = dp[i-1][b][g-1];
bVal = b;
gVal = g - 1;
}
else {
dp[i][b][g] = dp[i-1][b][g] +prices[i].getDiscountedPrice();
bVal = b;
gVal = g;
}
}
}
parentValues[i][b][g] = new BGValues(bVal, gVal);
}
}
}
The recurrence is implemented using multiple loops. At every stage, the value of dp[i][b][g] is computed. In addition, the parent of every node is also computed. For instance, parentValues[i][b][g] = new BGValues(bVal, gVal)
would assign (B,G) as the parent of (i,b,g) at values of b=0,g=0,G<1. This is useful to backtrack and fetch the path followed to reach the final state of (n,B,G) .
// Backtracking with parents to fetch the price considered for every // individual productint b1 = B, g1 = G, b2, g2;
for (int j = N; j > 0; j--) {
b2 = parentValues[j][b1][g1].getB();
g2 = parentValues[j][b1][g1].getG(); // actual price considered for the product
final double finalPriceToBePaid = dp[j][b1][g1] -
dp[j-1][b2][g2];
b1 = b2;
g1 = g2;
}
Prices for individual products can be retrieved by subtracting values from parent-child dp values. As a result, the subtracted value for every node in a path would give the price considered to arrive at the final value: the price considered would determine how that product was bought, whether combined in a BG set or bought at its discounted price.
Complexity Analysis
The algorithm runs with a complexity that is linear to n*B*G . This would allow an individual runtime (without optimizations/io/network latency) of at most 1s for n*B*G=100,000,000 (100 Million) on most compute instances.
Memory wise, this would work very well if n*B*G=10,000,000 (10 Million), running again linear to n*B*G. Considering 4 bytes for every integer stored in dp(i,b,g) . This would be in the order of a few 100 MBs.
Formulating recurrence relations and introducing dynamic programming can help solve a myriad of problems involving online retail, discount constructs in carts only accounting for a fraction of them.
