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.

Practice

1. What is the main goal of the Fractional Knapsack Problem?

easy

A. Maximize total value by taking fractions of items within weight limit

B. Minimize total weight of items selected

C. Select only whole items to maximize value

D. Sort items by weight only

Solution

1. Step 1: Understand problem goal

   The fractional knapsack problem allows taking parts of items to maximize value within a weight limit.

2. Step 2: Compare options

   Maximize total value by taking fractions of items within weight limit correctly states maximizing total value by taking fractions. Others focus on minimizing weight or whole items only, which is incorrect.

3. Final Answer:

   Maximize total value by taking fractions of items within weight limit -> Option A

4. Quick Check:

   Fractional knapsack = maximize value with fractions [OK]

Hint: Remember: fractional means partial items allowed [OK]

Common Mistakes:

• Thinking only whole items can be taken
• Confusing minimization with maximization
• Ignoring fractional parts of items

2. Which TypeScript syntax correctly declares an array of objects representing items with weight and value for the fractional knapsack?

easy

A. var items = weight: 10, value: 60; weight: 20, value: 100;

B. let items = (weight: 10, value: 60), (weight: 20, value: 100);

C. items = [{10, 60}, {20, 100}];

D. const items = [{weight: 10, value: 60}, {weight: 20, value: 100}];

Solution

1. Step 1: Check array and object syntax

   const items = [{weight: 10, value: 60}, {weight: 20, value: 100}]; uses correct array of objects syntax with curly braces and key-value pairs.

2. Step 2: Identify syntax errors in other options

   Options A, B, and D have invalid TypeScript syntax for arrays or objects.

3. Final Answer:

   const items = [{weight: 10, value: 60}, {weight: 20, value: 100}]; -> Option D

4. Quick Check:

   Array of objects syntax = const items = [{weight: 10, value: 60}, {weight: 20, value: 100}]; [OK]

Hint: Use square brackets for arrays and curly braces for objects [OK]

Common Mistakes:

• Using parentheses instead of square brackets for arrays
• Missing key names in objects
• Incorrect object literal syntax

3. What is the output of this TypeScript code snippet for fractional knapsack?

const items = [
  {weight: 10, value: 60},
  {weight: 20, value: 100},
  {weight: 30, value: 120}
];
const capacity = 50;

function fractionalKnapsack(items, capacity) {
  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
  let totalValue = 0;
  let remaining = capacity;
  for (const item of items) {
    if (item.weight <= remaining) {
      totalValue += item.value;
      remaining -= item.weight;
    } else {
      totalValue += item.value * (remaining / item.weight);
      break;
    }
  }
  return totalValue;
}

console.log(fractionalKnapsack(items, capacity));

medium

A. 200

B. 220

C. 240

D. 180

Solution

1. Step 1: Sort items by value/weight ratio

   Ratios: 60/10=6, 100/20=5, 120/30=4. Sorted order: item1, item2, item3.

2. Step 2: Add items until capacity 50

   Take item1 fully (weight 10, value 60), remaining 40.
   Take item2 fully (weight 20, value 100), remaining 20.
   Take 20/30 fraction of item3: value = 120 * (20/30) = 80.
   Total value = 60 + 100 + 80 = 240.

3. Step 3: Check options

   Matches 240.

4. Final Answer:

   240 -> Option C

5. Quick Check:

   Sum values with fractions = 240 [OK]

Hint: Sort by value/weight ratio, take full items first [OK]

Common Mistakes:

• Not sorting items by value/weight ratio
• Taking items without fractions
• Incorrect fraction calculation

4. Identify the bug in this TypeScript function for fractional knapsack:

function fractionalKnapsack(items, capacity) {
  items.sort((a, b) => (a.value / a.weight) - (b.value / b.weight));
  let totalValue = 0;
  let remaining = capacity;
  for (const item of items) {
    if (item.weight <= remaining) {
      totalValue += item.value;
      remaining -= item.weight;
    } else {
      totalValue += item.value * (remaining / item.weight);
      break;
    }
  }
  return totalValue;
}

medium

A. Using 'let' instead of 'const' for totalValue

B. Sorting order is ascending instead of descending by value/weight

C. Missing return statement

D. Incorrect fraction calculation in else block

Solution

1. Step 1: Analyze sorting function

   The sort compares (a.value/a.weight) - (b.value/b.weight), which sorts ascending by ratio.

2. Step 2: Understand impact on knapsack

   Fractional knapsack requires descending order to pick highest value/weight first. Ascending order causes wrong selection.

3. Final Answer:

   Sorting order is ascending instead of descending by value/weight -> Option B

4. Quick Check:

   Sort descending by ratio [OK]

Hint: Sort descending by value/weight ratio, not ascending [OK]

Common Mistakes:

• Sorting ascending instead of descending
• Ignoring sorting impact on result
• Confusing variable declarations

5. Given items with weights and values: [{weight: 5, value: 30}, {weight: 10, value: 40}, {weight: 20, value: 140}], and a knapsack capacity of 15, what is the maximum value achievable using the fractional knapsack approach?

hard

A. 105

B. 90

C. 120

D. 100

Solution

1. Step 1: Calculate value/weight ratios and sort descending

   Ratios: 30/5=6, 40/10=4, 140/20=7.
   Sorted order: item3 (7), item1 (6), item2 (4).

2. Step 2: Fill knapsack capacity 15

   Take item3 partially: since 20 > 15, value = 140 * (15/20) = 105.
   Total value = 105.
   Remaining capacity 0, stop.

3. Final Answer:

   105 -> Option A

4. Quick Check:

   Fractional knapsack max value = 105 [OK]

Hint: Sort by ratio, take full items, then fraction of next [OK]

Common Mistakes:

• Not sorting by value/weight ratio
• Trying to take full items exceeding capacity
• Miscomputing fractional values