Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
- //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]);
- //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);
Add Comment
Please, Sign In to add comment