What is the algorithm to determine the best way to distribute these coupons?

Question

Here is my problem. Imagine I am buying 3 different items, and I have up to 5 coupons. The coupons are interchangeable, but worth different amounts when used on different items.

Here is the matrix which gives the result of spending different numbers of coupons on different items:

coupons:    1         2         3         4         5
item 1      $10 off   $15 off
item 2                $5 off    $15 off   $25 off   $35 off
item 3      $2 off

I have manually worked out the best actions for this example:

• If I have 1 coupon, item 1 gets it for $10 off
• If I have 2 coupons, item 1 gets them for $15 off
• If I have 3 coupons, item 1 gets 2, and item 3 gets 1, for $17 off
• If I have 4 coupons, then either:
  • Item 1 gets 1 and item 2 gets 3 for a total of $25 off, or
  • Item 2 gets all 4 for $25 off.
• If I have 5 coupons, then item 2 gets all 5 for $35 off.

However, I need to develop a general algorithm which will handle different matrices and any number of items and coupons.

I suspect I will need to iterate through every possible combination to find the best price for n coupons. Does anyone here have any ideas?

Answer 1

This seems like a good candidate for dynamic programming:

//int[,] discountTable = new int[NumItems][NumCoupons+1]

// bestDiscount[i][c] means the best discount if you can spend c coupons on items 0..i
int[,] bestDiscount = new int[NumItems][NumCoupons+1];

// the best discount for a set of one item is just use the all of the coupons on it
for (int c=1; c<=MaxNumCoupons; c++)
    bestDiscount[0, c] = discountTable[0, c];

// the best discount for [i, c] is spending x coupons on items 0..i-1, and c-x coupons on item i
for (int i=1; i<NumItems; i++)
    for (int c=1; c<=NumCoupons; c++)
        for (int x=0; x<c; x++)
            bestDiscount[i, c] = Math.Max(bestDiscount[i, c], bestDiscount[i-1, x] + discountTable[i, c-x]);

At the end of this, the best discount will be the highest value of bestDiscount[NumItems][x]. To rebuild the tree, follow the graph backwards:

edit to add algorithm:

//int couponsLeft;

for (int i=NumItems-1; i>=0; i++)
{
    int bestSpend = 0;
    for (int c=1; c<=couponsLeft; c++)
        if (bestDiscount[i, couponsLeft - c] > bestDiscount[i, couponsLeft - bestSpend])
            bestSpend = c;

    if (i == NumItems - 1)
        Console.WriteLine("Had {0} coupons left over", bestSpend);
    else
        Console.WriteLine("Spent {0} coupons on item {1}", bestSpend, i+1);

    couponsLeft -= bestSpend;
}
Console.WriteLine("Spent {0} coupons on item 0", couponsLeft);

Storing the graph in your data structure is also a good way, but that was the way I had thought of.

Answer 2

It's the Knapsack problem, or rather a variation of it. Doing some research on algorithms related to this problem will point you in the best direction.