Minimize price for volume discount orders

Question

Hi all – I’m trying to put together a system to suggest consumable kits based on a requested quantity. The challenge I’m running into is that the kits have volume/bulk discounts, so it may be cheaper for the customer to order a larger quantity because the price may be less. For example, let’s say the available kits are:

• 25 widgets for $15
• 10 widgets for $7
• 5 widgets for $4
• 1 widget for $1

Right now, for a requested quantity of 74, my algorithm will suggest 2 x 25, 2 x 10, and 4 x 1 = $48. It would be cheaper however for the customer to just order 3 x 25 = $45.

Any thoughts on how to tackle this? I’m coding in C#.

Thanks!

Answer 1

Well, starting with the 25th unit, the price is $0.60/item. So if the customer orders more than 25, forget the packages that you are calculating and just multiply the quantity by $0.60.

Answer 2

That looks like standard DP (dynamic programming).

// bestPrice is array of best prices for each amount
// initially it's [0, INFINITY, INFINITY, INFINITY, ...]

for (int i = 0; i <= 74; ++i) {
    for (Pack pack : packs) {
        // if (i + pack.amount) can be achieved with smaller price, do it
        int newPrice = bestPrice[i] + pack.price;
        if (newPrice < bestPrice[i + pack.amount]) {
            bestPrice[i + pack.amount] = newPrice;
        }
    }
}

The answer is min(bestPrice[74], bestPrice[74 + 1], ... bestPrice[74 + 25 - 1]). Overhead 25 - 1 is obviously enough, because otherwise you would remove one pack and amount would still be >= 74.

Some links on the topic:
http://en.wikipedia.org/wiki/Dynamic_programming
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

edit
You can find optimal solution if you modify it a little. Add lastPack array, so lastPack[i] is the size of the package you used to achieve amount i. I guess, you can figure out how to update pseudo-code above.

Once algorithm is finished, you can get solution like this

int total = 74;
while (total > 0) {
    // package of size lastPack[total] was used to get amount 'total'
    // do whatever you want with this number here

    total -= lastPack[total];
}

Answer 3

So you are actually going to have to manually determine all of the breakpoints for items under a order of 25. Then basically use a lookup table type scenario to determine what to order for qty's less than 25. AS pointed out previously this is very similar to the Knapsack problem.

Basically your code would look something like;

int qtyOrder;
int qtyRemain;
int qty25pack;
int qty10pack;
int qty5pack;
int qty1pack;

//Grab as many 25 packs as possible
qty25pack = (qtyOrder % 25);
qtyRemain -= qty25Pack * 25;

//Here use your lookup table to determine what to order
// for the qty's that are less than 25

You could use some kind of greedy algorithm to determine it on the fly. Which would be ideal if the prices are expected to change a lot.

That could look something like filling the package size with an exact match and then determining the closest match that is just over the qty remaining and see if it is cheaper.

So for example:

//find the perfect product amount price
While (qtyRemain != 0) {
perfectPrice += (qtyRemain % nextSmallestSize) * nextSmallestPackagePrice;
qtyRemain -= (qtyReamin % nextSmallestSize)
}

//Find the closest match over price
While ((qtyRemain % nextSmallestSize) != 0){
closePrice += (qtyRemain % nextSmallestSize) * nextSmallestPackagePrice;
qtyRemain -= (qtyRemain % nextSmallestSize)
}
//add the last price before we reached the perfect price size
closePrice += nextSmallestPackagePrice;

//determine lowest price
if closePrice < perfectPrice {
 cost = closePrice;
}
else {
 cost = PerfectPrice;
}

This code is no where near complete but should give you an idea. Code is also probably not the greatest either.

Edit

The second chunk of code would go after the first chunk in place of the lookup