Case Study 2: Rosa's Budget Optimization — Greedy Allocation of Limited Funds Across Expense Categories

The Scenario

Rosa Martinelli is a freelance graphic designer with a monthly budget of $2,000. She has identified eight spending categories, each with a "satisfaction ceiling" — the maximum she can usefully spend — and a satisfaction-per-dollar rating (how much each dollar improves her quality of life).

Rosa's budget ($2,000) is not enough to cover all maximum spends (total: $2,500). She needs an allocation strategy.

Greedy Approach: Highest Satisfaction-Per-Dollar First

The greedy algorithm sorts by satisfaction-per-dollar (descending) and allocates money top-down:

1. Rent:         $800  (sat/$ = 10.0)  Remaining: $1,200
2. Healthcare:   $200  (sat/$ = 9.0)   Remaining: $1,000
3. Food:         $400  (sat/$ = 8.5)   Remaining: $600
4. Internet:     $100  (sat/$ = 7.5)   Remaining: $500
5. Transport:    $250  (sat/$ = 6.0)   Remaining: $250
6. Entertainment: $150 (sat/$ = 5.0)   Remaining: $100
7. Clothing:     $100  (sat/$ = 4.0)   Remaining: $0
8. Savings:      $0    (sat/$ = 3.0)   Remaining: $0

Total satisfaction: 8,000 + 1,800 + 3,400 + 750 + 1,500 + 750 + 400 = 16,600

Why Greedy Works Here

This is essentially the fractional knapsack problem. Rosa can allocate any dollar amount to any category (fractional allocation). The greedy strategy of spending on the highest-satisfaction-per-dollar category first is provably optimal because:

1. Each dollar spent in a higher-rated category produces more satisfaction than a dollar in a lower-rated one.
2. There is no interdependence between categories — spending on food does not affect the satisfaction from healthcare.
3. Partial allocations are allowed — she can spend less than the maximum on any category.

What If Rosa Cannot Split Allocations?

Now suppose Rosa is choosing between fixed "packages" — she either buys a full gym membership ($100) or does not; she either renews her annual transit pass ($250) or does not. This transforms the problem into 0/1 knapsack, and greedy may fail.

DP Solution for Fixed Packages

program RosaBudgetDP;

const
  N = 8;
  BUDGET = 2000;

type
  TPackage = record
    Name: string[20];
    Cost: Integer;
    Satisfaction: Integer;
  end;

var
  Packages: array[0..N-1] of TPackage;
  DP: array[0..N, 0..BUDGET] of Integer;
  I, W: Integer;

begin
  { Define packages }
  Packages[0].Name := 'Rent';          Packages[0].Cost := 800;  Packages[0].Satisfaction := 8000;
  Packages[1].Name := 'Food';          Packages[1].Cost := 400;  Packages[1].Satisfaction := 3400;
  Packages[2].Name := 'Healthcare';    Packages[2].Cost := 200;  Packages[2].Satisfaction := 1800;
  Packages[3].Name := 'Transport';     Packages[3].Cost := 250;  Packages[3].Satisfaction := 1500;
  Packages[4].Name := 'Internet';      Packages[4].Cost := 100;  Packages[4].Satisfaction := 750;
  Packages[5].Name := 'Entertainment'; Packages[5].Cost := 150;  Packages[5].Satisfaction := 750;
  Packages[6].Name := 'Clothing';      Packages[6].Cost := 100;  Packages[6].Satisfaction := 400;
  Packages[7].Name := 'Savings';       Packages[7].Cost := 500;  Packages[7].Satisfaction := 1500;

  { Initialize DP table }
  for I := 0 to N do
    for W := 0 to BUDGET do
      DP[I][W] := 0;

  { Fill DP table }
  for I := 1 to N do
    for W := 1 to BUDGET do begin
      DP[I][W] := DP[I-1][W];  { Don't take item I }
      if (Packages[I-1].Cost <= W) and
         (DP[I-1][W - Packages[I-1].Cost] + Packages[I-1].Satisfaction > DP[I][W]) then
        DP[I][W] := DP[I-1][W - Packages[I-1].Cost] + Packages[I-1].Satisfaction;
    end;

  { Output optimal selection }
  WriteLn('Optimal Budget Allocation (DP):');
  WriteLn('  Maximum satisfaction: ', DP[N][BUDGET]);
  WriteLn;
  WriteLn('  Selected packages:');
  W := BUDGET;
  for I := N downto 1 do
    if DP[I][W] <> DP[I-1][W] then begin
      WriteLn('    ', Packages[I-1].Name:15, ': $', Packages[I-1].Cost,
              ' (satisfaction: ', Packages[I-1].Satisfaction, ')');
      W := W - Packages[I-1].Cost;
    end;
  WriteLn('  Unspent: $', W);
end.

Output

Optimal Budget Allocation (DP):
  Maximum satisfaction: 16600

  Selected packages:
       Clothing: $100 (satisfaction: 400)
    Entertainment: $150 (satisfaction: 750)
       Transport: $250 (satisfaction: 1500)
        Internet: $100 (satisfaction: 750)
      Healthcare: $200 (satisfaction: 1800)
            Food: $400 (satisfaction: 3400)
            Rent: $800 (satisfaction: 8000)
  Unspent: $0

In this particular case, the greedy and DP solutions agree — the budget is just barely enough to cover 7 of the 8 categories, and the one excluded (Savings, lowest satisfaction-per-dollar) is the one both algorithms skip.

A Case Where They Diverge

Modify the problem: budget = $1,500 and add a "Vacation" package at $900 with satisfaction 5,000.

Greedy (by satisfaction-per-dollar): takes Rent ($800), Healthcare ($200), Food ($400) = $1,400, then $100 left for Internet. Total: 13,950.

DP might find: Rent ($800) + Vacation ($900) is not possible ($1,700 > $1,500). But other combinations like Vacation ($900) + Food ($400) + Internet ($100) + Clothing ($100) = $1,500, satisfaction = 5,000 + 3,400 + 750 + 400 = 9,550 — which is worse. So greedy wins in this case too.

The point is that you must verify — do not assume greedy is correct without proof or testing against DP on representative inputs.

Lessons for PennyWise

1. Greedy budget allocation works when spending is continuous (any amount in any category).
2. DP is needed for discrete choices (fixed-price packages, subscriptions, all-or-nothing decisions).
3. The PennyWise budget advisor should use greedy for continuous allocation (daily spending targets) and DP for monthly subscription decisions.
4. Present both approaches to the user: greedy for quick suggestions, DP for guaranteed optimal plans.

Discussion Questions

1. Rosa's satisfaction-per-dollar ratings are subjective. How would uncertainty in these ratings affect the choice between greedy and DP?
2. What if some categories are interdependent — e.g., spending on Healthcare reduces needed Transport spending? How would you model this?
3. Rosa could set aside money for savings. Should savings have a "satisfaction" rating? How does the time value of money affect this analysis?
4. If Rosa's income varies monthly (freelancer), how would you adapt the budget optimizer to handle uncertainty?