Case Study 1: The Knapsack Problem Three Ways — Brute Force, Greedy, and Dynamic Programming

The Problem

A backpacker is packing for a hike. Their pack can hold at most 15 kg. They have 6 items to choose from:

Which items should they take to maximize total utility?

Approach 1: Brute Force

Try all 2⁶ = 64 possible subsets and find the one with the highest value that fits within the weight limit.

procedure BruteForceKnapsack;
const
  N = 6;
  Cap = 15;
  Weights: array[0..N-1] of Integer = (2, 3, 5, 7, 4, 1);
  Values: array[0..N-1] of Integer = (15, 12, 20, 25, 18, 5);
  Names: array[0..N-1] of string = (
    'Water filter', 'First aid', 'Sleeping bag',
    'Tent', 'Extra food', 'Camera');
var
  Mask, BestMask: Integer;
  I, TotalW, TotalV, BestV: Integer;
  Subsets: Integer;
begin
  BestV := 0;
  BestMask := 0;
  Subsets := 1 shl N;  { 2^N }

  for Mask := 0 to Subsets - 1 do begin
    TotalW := 0;
    TotalV := 0;
    for I := 0 to N - 1 do
      if (Mask and (1 shl I)) <> 0 then begin
        TotalW := TotalW + Weights[I];
        TotalV := TotalV + Values[I];
      end;

    if (TotalW <= Cap) and (TotalV > BestV) then begin
      BestV := TotalV;
      BestMask := Mask;
    end;
  end;

  WriteLn('Brute Force Result (checked ', Subsets, ' subsets):');
  WriteLn('  Total value: ', BestV);
  Write('  Items: ');
  for I := 0 to N - 1 do
    if (BestMask and (1 shl I)) <> 0 then
      Write(Names[I], ' (', Weights[I], 'kg) ');
  WriteLn;
end;

Result: Water filter + First aid + Sleeping bag + Extra food + Camera = value 70, weight 15 kg. Subsets checked: 64. For N = 30: 2³⁰ ≈ 1 billion subsets. Impractical.

Approach 2: Greedy (by Value/Weight Ratio)

Sort items by value-per-weight ratio (descending). Take items greedily until the pack is full.

Sorted by ratio: Water filter (7.50), Camera (5.00), Extra food (4.50),
                 First aid (4.00), Sleeping bag (4.00), Tent (3.57)

Take Water filter: weight=2, value=15, remaining=13
Take Camera: weight=1, value=5, remaining=12
Take Extra food: weight=4, value=18, remaining=8
Take First aid: weight=3, value=12, remaining=5
Take Sleeping bag: weight=5, value=20, remaining=0
Cannot take Tent (weight=7 > remaining=0)

Greedy result: Value = 70, weight = 15 kg. Items: Water filter + Camera + Extra food + First aid + Sleeping bag.

In this case, greedy happens to find the optimal solution! But that is a coincidence, not a guarantee.

Approach 3: Dynamic Programming

Build a table where DP[i][w] = maximum value achievable using items 1..i with capacity w.

The DP table (abbreviated):

       Cap:  0   1   2   3   4   5  ...  15
Item 0:      0   0   0   0   0   0  ...   0
Water(2,15): 0   0  15  15  15  15  ...  15
Aid(3,12):   0   0  15  15  15  27  ...  27
Bag(5,20):   0   0  15  15  15  27  ...  65
Tent(7,25):  0   0  15  15  15  27  ...  70
Food(4,18):  0   0  15  15  18  27  ...  70
Camera(1,5): 0   5  15  20  20  23  ...  70

DP result: Value = 70, weight = 15 kg. Same as brute force (guaranteed optimal).

When Greedy Fails

Modify the problem slightly: capacity = 10, items = [(6, 8), (5, 7), (5, 7)].

• Greedy (by ratio): Takes item 1 (ratio 1.33), weight = 6. Cannot fit item 2 or 3. Total value = 8.
• DP: Takes items 2 and 3, weight = 10. Total value = 14.

Greedy missed the optimal solution because it committed to the highest-ratio item, which used too much capacity.

Performance Comparison

Key Lessons

1. Brute force is correct but exponentially slow. Use only for tiny inputs or as a reference for testing.
2. Greedy is fast and simple but not always correct. It works for the fractional knapsack but can fail for 0/1.
3. DP is correct and efficient (pseudo-polynomial). It is the right choice for 0/1 knapsack in practice.
4. Always test greedy against brute force on small inputs before trusting it on large ones.

Discussion Questions

1. If you could take fractions of items, which approach would be optimal? (Hint: this changes the problem to fractional knapsack.)
2. How would you modify the DP solution if you could take up to 3 copies of each item?
3. The DP solution uses O(n × W) memory. How could you reduce this to O(W)?
4. For very large W (e.g., W = 10⁹), DP becomes impractical. What approach would you use instead?