Algorithm to price bulk discounts

Question

Hi, i am designing a Chinese auction website.

Tickets ($5, $10 & $20) are sold either individually, or via packages to receive discounts. There are various Ticket packages for example:

1. 5-$5 tickets = receive 10% off
2. 5-$10 tickets = receive 10% off
3. 5-$20 tickets = receive 10% off
4. 5-$5 tickets + 5-$10 tickets + 5-$20 tickets = receive 15% off

When users add tickets to their cart, i need to figure out the cheapest package(s) to give them. the trick is that if a user adds 4-$5 tickets + 5-$10 tickets + 5-$20 tickets, it should still give him package #4 since that would be the cheapest for him.

Any help in figuring out a algorithm to solve this, or any tips would be greatly appreciate it.

thanks

EDIT

i figured out the answer, thanks all, but the code is long.

i will post the answer code if anyone still is interested.

Answer 1

One approach is dynamic programming.

The idea is that if the buyer wants x of item A, y of item B, and z of item C, then you should compute for all triples (x', y', z') with 0 <= x' <= x and 0 <= y' <= y and 0 <= z' <= z the cheapest way to obtain at least x' of A, y' of B, and z' of C. Pseudocode:

for x' = 0 to x
    for y' = 0 to y
        for z' = 0 to z
            cheapest[(x', y', z')] = min over all packages p of (price(p) + cheapest[residual demand after buying p])
            next_package[(x', y', z')] = the best package p

Then you can work backward from (x, y, z) adding to the cart the packages indicated by next_package.

If there are many different kinds of items or there are many of each item, branch and bound may be a better choice.

Answer 2

First, calculate how many full Package 4s you need. Get them out of the way.

full_package_4_count = min(x, y, z) mod 5.

x = x - 5 * full_package_4_count
y = y - 5 * full_package_4_count
z = z - 5 * full_package_4_count

Now, there may still be worth buying some more Package 4s, even though they didn't actually want to buy that many tickets.

How many of them could there be?

partial_package_4_max = (max(x, y, z) + 4) mod 5

Now loop to try each of these out:

best_price = 10000000
for partial_package_4_count = 0 to partial_package_4_max:
    -- Calculate how much we have already spent.
    price = (full_package_4_count + partial_package_4_count) * 175 * (1-0.15)

    -- Work out how many additional tickets we want.
    x' = max(0, x - 5 * partial_package_count)
    y' = max(0, y - 5 * partial_package_count)
    z' = max(0, z - 5 * partial_package_count)

    --- Add cost for additional tickets (with a 10% discount for every pack of 5)
    price = price + x' mod 5 * 25 * (1-0.10) + x' div 5 * 5
    price = price + y' mod 5 * 50 * (1-0.10) + x' div 5 * 10
    price = price + y' mod 5 * 100 * (1-0.10) + x' div 5 * 20

    if price < best_price
        best_price = price
        -- Should record other details about the current deal here too.

Answer 3

After selling the customer as many complete packages as possible, we are left with some residual N of tickets desired of each of the 3 types ($5, $10, $20). In the example you gave, the quantities desired range from 0 to 5 (6 possible values). Thus, there are only 214 possible residual combinations (6 ** 3 - 2; minus 2 because the combinations 0-0-0 and 5-5-5 are degenerate). Just pre-compute the price of each combination as though it were purchased without package 4; compare that calcuation to the cost of package 4 ($148.75); this will tell you the cheapest approach for every combination.

Is the actual number of packages so large that a complete pre-computation wouldn't be a viable approach?

Answer 4

Hello to all, I am trying to predict the bottle pricing for spirits in the state of Ohio. Any ideas?