I'm looking at finding a solution to the following problem, but I'm having trouble formulating it sensibly, and then finding an appropriate algorithm to solve it.
Consider a list of items placed in a shopping bag: 1, 2, 3, 4...
Each item can be part of one or more promotions: A, B, C, D
We wish to apply the set of promotions such that we maximise the value of the discount, that no item is allowed to participate in more than one promotion, but each promotion could be applied more than once.
Promotions can be defined in a number of ways, but for now I'm just considering a type of 'Buy 2 qualifying items, save X', I'm hopeful I'll be able to generalise from here.
My example would be:
- Promotion A - Buy 2 Save 8
- Promotion B - Buy 2 Save 10
Promotion C - Buy 2 Save 6
Item 1 - Eligible for A, B
- Item 2 - Eligible for B
- Item 3 - Eligible for A, C
- Item 4 - Eligible for B, C
It's quite easy to see here that the correct application of promotions is A to Item 1, 3 and B to 2, 4. This gives a total discount of 18.
In a larger case it becomes difficult, hence needing to solve algorithmically.
I've tried the following:
- List all the possible combinations of Promotions we could apply.
- Discard any that are obviously poor (e.g. a direct copy of a promotion with a higher value).
- Apply any that have no overlap with other promotions (e.g. If Item 1 and 2 are only valid for promotion A, then apply that promotion).
- Take the remaining set and attempt a branch-and-bound type search on the results.
However, this can take a long time (for large sets with similar discounts).
I feel this is a type of Knapsack or Assignment problem, but I can't write it sensibly. Without being able to write it sensibly I can't solve it.
Is this a recognised variant of a problem? Any help attacking it would be greatly appreciated, especially with psuedo-code to help solve it