Maximize Cashback Rewards

Comparing Brute Force and Greedy algorithms to find the optimal credit card assignment for maximum cashback

Brute Force Greedy Optimization Java HTML JavaScript CSS
Try the Demo

About the Project

A project comparing Brute Force and Greedy algorithms to find the optimal credit card assignment for maximum cashback. Given multiple credit cards with different cashback rates per spending category and individual spending limits, the system determines which card to use for each category to maximize total cashback.

The core logic was originally implemented in Java as an algorithms course project, then re-implemented as an interactive web demo where users can input their own cards, categories, and rates and see both algorithms run side-by-side in real time.

How It Works

1

Define Your Cards

Set how many credit cards you have and the maximum you can spend on each one.

2

Set Categories

Enter what you spend in each category (e.g. groceries, gas) and each card's cashback percentage for that category.

3

Run Algorithms

Click "Run Algorithms" and both methods will figure out which card to use for each category to get you the most cashback.

4

Compare Results

See the results side by side and check whether both methods agree or one found a better answer.

What to Expect — Possible Outcomes

Both algorithms agree

Both Brute Force and Greedy found the same total cashback. This means the Greedy shortcut happened to find the best possible answer.

Example You have 2 cards with generous limits and 3 categories. Each category clearly has one card with a much better rate. Both methods pick the same cards and return the same cashback total (e.g. $116.00).

One algorithm found a better solution

Brute Force found a higher cashback than Greedy (or vice versa in rare edge cases). This shows that taking the "obvious best" choice at each step does not always lead to the best overall result.

Example Card A has the best rate for both groceries ($500) and gas ($300), but its limit is $600. Greedy assigns groceries to Card A first (biggest spend), using up the limit so gas goes to a worse card. Brute Force discovers that assigning gas to Card A and groceries elsewhere actually earns more cashback overall.

No valid assignment found

The total spending across all categories exceeds what the cards can handle. No combination of card assignments can stay within every card's limit.

Example You have 2 cards with limits of $500 each ($1,000 total), but your categories add up to $1,200. There is simply not enough room on the cards, so both algorithms report failure.

Interactive Demo

Rebuilds the input tables below to match
the number of cards and categories you set.

Spending per Category ($)

Card Spending Limits ($)

Cashback Rates (%) — rows: cards, columns: categories

Runs both Brute Force and Greedy on your current inputs and shows results side by side.
Fills the tables with a pre-built example so you can see how the demo works.
Generates random spending amounts, limits, and cashback rates to experiment with.

Algorithm Breakdown

Brute Force

Time Complexity: O(nm)

  • Generates all possible assignments of categories to cards
  • For each assignment, checks if card limits are respected
  • Calculates cashback for every valid assignment
  • Returns the assignment with maximum cashback
  • Guarantees the optimal solution
  • Becomes impractical for large inputs (e.g. 5 cards, 15 categories = 30 billion assignments)

Greedy

Time Complexity: O(n × m)

  • Sorts categories by spending amount (largest first)
  • For each category, picks the card with the highest cashback rate
  • Only considers cards that still have room under their limit
  • Runs in polynomial time, scales to any input size
  • Does not guarantee the optimal solution
  • May differ from brute force when card limits force suboptimal local choices

Team

Khalid Al Dosari

Zeyad bin Nazir

Abdulellah Altowaijri