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

This can be written as a linear programming problem. For most 'typical' problems, the simplex method is a fast, relatively simple way to solve such problems, or there are open source LP solvers available.

For your example:

Let 0 <= xi <= 1

• x1 = One if one coupon is spent on item 1, zero otherwise
• x2 = One if two coupons are spent on item 1, zero otherwise
• x3 = One if one coupon is spent on item 2, zero otherwise
• x4 = One if two coupons are spent on item 2, zero otherwise
• x5 = One if three coupons are spent on item 3, zero otherwise
• ...

Assume that if I spend two coupons on item 1, then both x1 and x2 are one. This implies the constraint

• x1 >= x2

With similar constraints for the other items, e.g.,

• x3 >= x4
• x4 >= x5

The amount saved is

• Saved = 10 x1 + 5 x2 + 0 x3 + 5 x4 + 10 x5 + ...

If you want to find the most money saved with a fixed number of coupons, then you want to minimize Saved subject to the constraints above and the additional constraint:

• coupon count = x1 + x2 + x3 + ...

This works for any matrix and number of items. Changing notation (and feeling sad that I can't do subscripts), let 0 <= y_ij <= 1 be one if j coupons are spent on item number i. The we have the constraints

• y_i(j-1) >= y_ij

If the amount saved from spending j coupons on item i is M_ij, where we define M_i0 = 0, then maximize

• Saved = Sum_ij (M_ij - M_i(j-1)) y_ij

subject to the above constraints and

• coupon count = Sum_ij y_ij

(The italics formatting doesn't seem to be working here)

Answer 3

I think dynamic programming should do this. Basically, you keep track of an array A[n, c] whose values mean the optimal discount while buying the n first items having spent c coupons. The values for a[n, 0] should be 0 for all values of n, so that is a good start. Also, A[0, c] is 0 for all c.

When you evaluate A[n,c], you loop over all discount offers for item n, and add the discount for that particular offer to A[n-1,c-p] where p is the price in coupons for this particular discount. A[n-1, c-p] must of course be calculated (in the same way) prior to this. Keep the best combination and store in the array.

A recursive implementation would probably give the cleanest implementation. In that case, you should find the answer in A[N,C] where N is the total number of items and C is the total number of available coupons.

Answer 4

I suspect some kind of sorted list for memoizing each coupon-count can help here.

for example, if you have 4 coupons, the optimum is possibly:

1. using all 4 on something. You have to check all these new prices.
2. using 3 and 1. either the 3-item is the optimal solution for 3 coupons, or that item overlaps with the three top choices for 1-coupon items, in which case you need to find the best combination of one of the three best 1-coupon and 3-coupon items.
3. using 2 and 2. find top 3 2-items. if #1 and #2 overlap, #1 and #3 , unless they also overlap, in which case #2 and #3 don't.

this answer is pretty vague.. I need to put more thought into it.

Answer 5

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.

Answer 6

This problem is similar in concept to the Traveling Salesman problem where O(n!) is the best for finding the optimal solution. There are several shortcuts that can be taken but they required lots and lots of time to discover, which I doubt you have.

Checking each possible combination is going to be the best use of your time, assuming we are dealing with small numbers of coupons. Make the client wait a bit instead of you spending years on it.