php [PHP] I need help on figuring out the algorithm for sorting discount to get maximum value.

[halfass]

So I have a system that allow multiple discount to be applied on a checkout.

 

The products can have more than one categories tag.

 

Each discounts have its own categories tags list that it is not allowed to be applied to. The discount only have fixed amount. No percentage.

 

The deal is as long as there is a product in the checkout that doesn't have the category that is listed in the discount, the discount can be used. Albeit the max amount will be limited to the applicable products. Any extra will be forfeited.
Example:

Discount A ($50) Excluded Category: [Accessory, Summer]

On Checkout:

Product A [Accessory, Winter] - $50

Product B [Shoe, Winter] - $30

 

In this case Discount A can be applied since it is applicable to Product B

Checkout with applied discount:

Product A [Accessory, Winter] - $30

Product B [Shoe, Winter] - $30

Discount A - ($30) - only $30 cause the only applicable amount is product B. $20 is forfeited.

 

Now here come the complex part. I need to apply algorithm where the maximum amount of discount could be achieve

Example:

Discount A ($30) Excluded Categories: none

Discount B ($40) Excluded Categories: [Shoe, Summer]

On Checkout:

Product A [Accessory, Winter] - $50

Product B [Shoe, Winter] - $50

If it were Simple Algorithm of first come first serve, the result will be 
On Checkout with discount:

Product A [Accessory, Winter] - $50

Product B [Shoe, Winter] - $50

Discount A - ($30) - applied discount for product A since product A came 1st
Discount B - ($20) - applied discount for the remaining value of product A. limited to $20 cause cannot apply discount to product B. the other $20 is forfeited

 

I need to make algorithm where it is smart enough to make use the full discount amount like this:

Product A [Accessory, Winter] - $50

Product B [Shoe, Winter] - $50

Discount A - ($30) - applied discount anywhere since the discount doesn't have any limitation(can be from single product or can be from summation of multiple products)
Discount B - ($40) - applied discount for product A.

 

Thank you in advance

[Bombastinator]

Is this inside an app like a database program or something? If so there might be shortcuts or better ways to do it.  Also such things may already have been figured out and all that might be needed is a download.  It seems the sort of problem that has come up in the past enough for it to be already solved elsewhere.

[halfass]

56 minutes ago, Bombastinator said:

Is this inside an app like a database program or something? If so there might be shortcuts or better ways to do it.  Also such things may already have been figured out and all that might be needed is a download.  It seems the sort of problem that has come up in the past enough for it to be already solved elsewhere.

Yes. It's a website built from php. I've tried to search for it. But never found it cause it's pretty specific. I'm pretty sure this kind of behavior algorithm have already been made and have its own name since this kind of algorithm can be used for a lot of applications. If anyone here know of it, I would be thankful for the information.

[JacobFW]

I feel like this could almost certainly be done using a subquery in your main select, but I'm not sure how you're schema is set up.

How are your categories stored related to the product?  Do you have a separate table with the product id and the category description/id, or is it just a text field in the product table that literally has "Accessory,Winter" as it's value?

 

 

[Bombastinator]

On 9/4/2022 at 11:08 AM, halfass said:

Yes. It's a website built from php. I've tried to search for it. But never found it cause it's pretty specific. I'm pretty sure this kind of behavior algorithm have already been made and have its own name since this kind of algorithm can be used for a lot of applications. If anyone here know of it, I would be thankful for the information.

Iirc excel had this built in.  You just had to know what it was

[Franck]

You are looking at a weird cartesian product algorithm.

the Cartesian Product algorithm all it does is generate all permutation possible and in your case you would want the lowest amount of all those combinaison.

 

But i would personally classify this algorithm as "classification bin packing" Where your bins represent the discount and have size equal to value but the classification

force and restrict the bin insertion.

 

Anyhow either are exponentially long to run. If you have 50 items and just 1 discount just order wise that is :

30,414,093,201,713,375,576,366,966,406,747,986,832,057,064,836,514,787,179,557,289,984 combinaisons

 

With just 10 items it is still 3,628,800 combinaison but if you have 2 discount that a crazy amount of combinaison.

 

Hope you can hardcode some logic and for order somehow or you can run either algorithm and do a breadth first search or settle for an okay value and not "the best"

[Just that Mario]

On 9/4/2022 at 5:44 PM, halfass said:

Example:

Discount A ($50) Excluded Category: [Accessory, Summer]

On Checkout:

Product A [Accessory, Winter] - $50

Product B [Shoe, Winter] - $30

 

In this case Discount A can be applied since it is applicable to Product B

Checkout with applied discount:

Product A [Accessory, Winter] - $30

Product B [Shoe, Winter] - $30

Discount A - ($30) - only $30 cause the only applicable amount is product B. $20 is forfeited.

Product B's cost was not reduced, product A's was. Also discount was 50 - 30 = 20, so 30 was lost. Am I missing something or your example is flawed?

Not certain, but should be able to form a tree structure?

What you can do is try sorting discounts in descending order. Then for each discount check to which product it can give the biggest discount. When product is at maximum discount or not applicable, skip it. You may also be able to sort products by price in descending order (or better yet by maximum applicable discount amount) and filter out all products from checking that do not match any discount categories.

 

discounts: [50, 40, 30]
product prices ([price, min]): [ [150, 100], [50, 25], [200, 100] ]

[ [150 - 50, 100], [50, 25], [200, 100] ]

[ [100, 100], [50, 25], [200, 100] ]

[ [100, 100], [50, 25], [200 - 40, 100] ]

[ [100, 100], [50, 25], [160, 100] ]

[ [100, 100], [50, 25], [160 - 30, 100] ]

[ [100, 100], [50, 25], [130, 100] ]

total price: 280

EDIT:

My suggested solution will not work for every case, but it can be used as a base to develop a working solution. Some things that can also help:

• sorting discounts and products by their category
• sorting products by maximum discount amount after a discount is used up.
• testing if using discount on given product gives maximum discount amount (waste of discount is 0).