code_junkie

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

Nov 13th, 2011
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.33 KB | None | 0 0
  1. coupons: 1 2 3 4 5
  2. item 1 $10 off $15 off
  3. item 2 $5 off $15 off $25 off $35 off
  4. item 3 $2 off
  5.  
  6. //int[,] discountTable = new int[NumItems][NumCoupons+1]
  7.  
  8. // bestDiscount[i][c] means the best discount if you can spend c coupons on items 0..i
  9. int[,] bestDiscount = new int[NumItems][NumCoupons+1];
  10.  
  11. // the best discount for a set of one item is just use the all of the coupons on it
  12. for (int c=1; c<=MaxNumCoupons; c++)
  13. bestDiscount[0, c] = discountTable[0, c];
  14.  
  15. // the best discount for [i, c] is spending x coupons on items 0..i-1, and c-x coupons on item i
  16. for (int i=1; i<NumItems; i++)
  17. for (int c=1; c<=NumCoupons; c++)
  18. for (int x=0; x<c; x++)
  19. bestDiscount[i, c] = Math.Max(bestDiscount[i, c], bestDiscount[i-1, x] + discountTable[i, c-x]);
  20.  
  21. //int couponsLeft;
  22.  
  23. for (int i=NumItems-1; i>=0; i++)
  24. {
  25. int bestSpend = 0;
  26. for (int c=1; c<=couponsLeft; c++)
  27. if (bestDiscount[i, couponsLeft - c] > bestDiscount[i, couponsLeft - bestSpend])
  28. bestSpend = c;
  29.  
  30. if (i == NumItems - 1)
  31. Console.WriteLine("Had {0} coupons left over", bestSpend);
  32. else
  33. Console.WriteLine("Spent {0} coupons on item {1}", bestSpend, i+1);
  34.  
  35. couponsLeft -= bestSpend;
  36. }
  37. Console.WriteLine("Spent {0} coupons on item 0", couponsLeft);
Add Comment
Please, Sign In to add comment