Is there an efficient algorithm for this ecommerce optimization problem?

Consider the problem of minimizing the checkout price of a shopping basket in the presence of some discount rules:

There are $$n \gt 0$$ distinct products in our shopping basket. Each product is associated with a price $$price_i \geq 0$$ and a quantity $$quantity_i \gt 0$$. Without applying any discounts, the checkout price is simply $$\Sigma_{i=1}^n price_i \times quantity_i$$.

There are 2 different product categories, Category A and Category B. Each product can be placed into either one of the categories, but certain products might be placed into both categories at the same time.

Discount works as follow: if $$a$$ pieces of products in Category A and $$b$$ pieces of products in Category B have been purchased, the full bundle of the $$(a+b)$$ pieces will cost a total of \$C. There are no constraints on \$C. It can be very very high and everyone would just ignore the discount.

For example, suppose $$n=2$$, $$a=2$$, $$b=3$$, $$C=100$$, we are buying product X (category A, price=30, quantity=3) and product Y (category B, price=40, quantity=3). The original price is $$30 \times 3 + 40 \times 3 = 210$$, but after applying the discount, it becomes $$100 + 30 = 130$$

Example 2: suppose $$n=4$$, $$a=1$$, $$b=1$$, $$C=20$$, we are buying product W (category A, price=30, quantity=3), product X (category A, price=40, quantity=3), product Y (category B, price=50, quantity=4) and product Z (in both categories A & B, price=60, quantity=4). The original price is $$30 \times 3 + 40 \times 3 + 50 \times 4 + 60 \times 4 = 650$$. Assuming the discount can only be applied once, we will apply the discount on product Z+Z, and the checkout price becomes $$30 \times 3 + 40 \times 3 + 50 \times 4 + 60 \times (4-2) + 20 = 550$$.

However, if the discount can be applied unlimited number of times, the optimal choice is to pair up all of the items, and the checkout price will be $$7 \times 20 = 140$$

Is there an efficient algorithm to compute the minimum checkout price if there is only 1 such discount rule and it can only be applied once? What if it can be applied unlimited number of times? What if there are multiple such discount rules?

Note that each piece of item in the basket can only be discounted once in any cases.

• Where does 5 come from? It comes out of nowhere. Do you mean $a+b$? Do you mean $n$?
– D.W.
Commented Nov 1, 2023 at 20:36
– D.W.
Commented Nov 1, 2023 at 20:37

The usual rule on this site is to ask only one question per post, so I'll answer the first question. Specifically, I'll focus on the case where there is only one discount rule, and it can only be applied once. In that case, the problem can be solved with a greedy algorithm:

• Let $$n_a := a, n_b := b, n_x := 0$$.

• Sort all the products, by decreasing price. (If a price has quantity higher than one, it is duplicated that many times in the sorted list.)

• While $$n_a>0$$ or $$n_b>0$$ or $$n_x>0$$ and the list is non-empty:

• Take the next product from the sorted list.
• If this product is of category A and B:
• If $$n_a>0$$ and $$n_b>0$$, set $$n_a := n_a-1$$ and $$n_b := n_b-1$$ and $$n_x := n_x+1$$ and mark this product.
• Otherwise, if $$n_a>0$$ and $$n_b=0$$, set $$n_a := n_a-1$$ and mark this product; if $$n_a=0$$ and $$n_b>0$$, set $$n_b := n_b-1$$ and mark this product; if $$n_a=0$$ and $$n_b=0$$ and $$n_x>0$$, set $$n_x := n_x-1$$ and mark this product.
• If this product is of category A only:
• If $$n_a>0$$, set $$n_a := n_a-1$$ and mark this product.
• Otherwise, if $$n_a=0$$ and $$n_x>0$$, set $$n_x := n_x-1$$ and mark this product.
• If this product is of category B only:
• If $$n_b>0$$, set $$n_b := n_b - 1$$ and mark this product.
• Otherwise, if $$n_b=0$$ and $$n_x>0$$, set $$n_x := n_x-1$$ and mark this product.
• At the end, if $$n_a=0$$ and $$n_b=0$$ and $$n_x=0$$, combine all marked products into the discount bundle. This is the optimal selection of items to use the discount on.

The intuition is that marked items are selected to be in the bundle, and we proceed down the list, from most expensive product to least expensive. At any intermediate stage of the algorithm, $$n_a$$ counts the number of additional items we need from category A to complete the bundle, $$n_b$$ counts the number of additional items we need from category B to complete the bundle, and $$n_x$$ counts the number of other items we need (they can be any category) to complete the bundle.

Regarding a discount code that can be applied an unlimited number of times, I suggest spending some time trying to figure out if you can adapt this greedy strategy to that case; if not, ask a new question about that case, and share what progress you've made.