Fractional Knapsack Problem in DSA Typescript

Mental Model

We want to fill a bag with items to get the most value, and we can take parts of items if needed.

Analogy: Imagine filling a jar with different types of honey jars. You want the sweetest honey first, and if the jar is almost full, you take only a part of the last honey jar to fill it exactly.

Items: [value/weight ratio]
[Item1: 60/10=6] -> [Item2: 100/20=5] -> [Item3: 120/30=4]
Knapsack capacity: 50
Knapsack: empty ↑

Dry Run Walkthrough

Input: items: [(value=60, weight=10), (value=100, weight=20), (value=120, weight=30)], capacity=50

Goal: Maximize total value in knapsack by taking whole or fractional items without exceeding capacity

Step 1: Sort items by value/weight ratio descending

[Item1: 60/10=6] -> [Item2: 100/20=5] -> [Item3: 120/30=4]

Why: We want to pick items with highest value per weight first to maximize total value

Step 2: Take whole Item1 (weight 10) into knapsack

Knapsack: 10/50 weight used, total value 60 ↑

Why: Item1 fits fully, so take it all to maximize value

Step 3: Take whole Item2 (weight 20) into knapsack

Knapsack: 30/50 weight used, total value 160 ↑

Why: Item2 fits fully, so take it all to maximize value

Step 4: Take fraction of Item3 to fill remaining capacity (20/30 fraction)

Knapsack: 50/50 weight used, total value 160 + (120 * 20/30) = 240 ↑

Why: Only part of Item3 fits, so take fraction to fill knapsack exactly

Result:

Knapsack full: total value 240, items taken: Item1 full, Item2 full, Item3 2/3 fraction

Annotated Code

DSA Typescript

class Item {
  value: number;
  weight: number;
  constructor(value: number, weight: number) {
    this.value = value;
    this.weight = weight;
  }
}

function fractionalKnapsack(items: Item[], capacity: number): number {
  // Sort items by value/weight ratio descending
  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));

  let totalValue = 0;
  let remainingCapacity = capacity;

  for (const item of items) {
    if (item.weight <= remainingCapacity) {
      // Take whole item
      totalValue += item.value;
      remainingCapacity -= item.weight;
    } else {
      // Take fraction of item
      totalValue += item.value * (remainingCapacity / item.weight);
      break; // Knapsack is full
    }
  }

  return totalValue;
}

// Driver code
const items = [new Item(60, 10), new Item(100, 20), new Item(120, 30)];
const capacity = 50;
const maxValue = fractionalKnapsack(items, capacity);
console.log(maxValue.toFixed(2));

items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));

Sort items by descending value-to-weight ratio to prioritize high value density

if (item.weight <= remainingCapacity) {

Check if whole item fits in remaining capacity

totalValue += item.value;

Add full item value to total

remainingCapacity -= item.weight;

Reduce remaining capacity by item weight

totalValue += item.value * (remainingCapacity / item.weight);

Add fractional value proportional to remaining capacity

break;

Stop after filling knapsack to capacity

Output

240.00

Complexity Analysis

Time: O(n log n) because we sort the n items by value-to-weight ratio

Space: O(1) additional space since sorting is in-place and only a few variables used

vs Alternative: Compared to 0/1 knapsack which is O(n*capacity), fractional knapsack is faster due to greedy sorting and no dynamic programming

Edge Cases

Empty items list

Returns 0 value since no items to take

DSA Typescript

for (const item of items) {

Capacity zero

Returns 0 value since knapsack cannot hold anything

DSA Typescript

if (item.weight <= remainingCapacity) {

Item with zero weight

Avoid division by zero error by assuming no zero weight items or handle separately

DSA Typescript

items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));

When to Use This Pattern

When you need to maximize value with divisible items and limited capacity, use the fractional knapsack pattern because greedy choice by value density gives optimal solution.

Common Mistakes

Mistake: Not sorting items by value-to-weight ratio before selection
Fix: Sort items descending by value/weight ratio to ensure greedy picks maximize value

Mistake: Trying to take whole items only, ignoring fractions
Fix: Allow fractional parts of items when capacity is insufficient for whole item

Mistake: Not breaking loop after filling knapsack with fraction
Fix: Break loop after adding fractional item to avoid overfilling

Summary

Find the maximum total value by taking whole or fractional parts of items within capacity.

Use when items can be divided and you want the best value-to-weight ratio first.

The key is sorting items by value density and taking as much as possible greedily.