Fractional Knapsack Problem in DSA Typescript - Execution Trace

Concept Flow - Fractional Knapsack Problem

Start with items sorted by value/weight ratio

↓

Initialize total weight = 0, total value = 0

↓

For each item in sorted list

↓

Can full item fit?

No→Take fraction of item to fill knapsack

|Yes↓

Add full item weight and value

↓

Update total weight and value

↓

Knapsack full?

No→Next item

|Yes↓

Done

The flow shows sorting items by value/weight, then adding full or fractional parts until knapsack is full.

Execution Sample

DSA Typescript

items = [{value:60, weight:10}, {value:100, weight:20}, {value:120, weight:30}]
capacity = 50
// sort items by value/weight descending
items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
let totalValue = 0;
let totalWeight = 0;
for (const item of items) {
  if (totalWeight + item.weight <= capacity) {
    totalWeight += item.weight;
    totalValue += item.value;
  } else {
    const remain = capacity - totalWeight;
    totalValue += item.value * (remain / item.weight);
    totalWeight = capacity;
    break;
  }
}
return totalValue;

This code picks items or fractions to maximize value within capacity.

Execution Table

Step	Operation	Item (value, weight)	Fraction Taken	Weight Added	Value Added	Total Weight	Total Value	Knapsack State
1	Sort items by value/weight	[(60,10), (100,20), (120,30)]	-	-	-	0	0	Items sorted by ratio: (60,10), (100,20), (120,30)
2	Take full item	(60,10)	1	10	60	10	60	60/10 -> 40/50 capacity left
3	Take full item	(100,20)	1	20	100	30	160	160/30 -> 20/50 capacity left
4	Take fraction	(120,30)	0.6667	20	80	50	240	160 + 80 = 240 total value, knapsack full
5	Stop	-	-	-	-	50	240	Knapsack capacity reached

💡 Knapsack weight reached capacity 50, no more items can be added.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
totalWeight	0	10	30	50	50
totalValue	0	60	160	240	240
fractionTaken	-	1	1	0.6667	-

Key Moments - 3 Insights

Why do we take only a fraction of the last item instead of the whole?

Because adding the whole last item would exceed the knapsack capacity. See step 4 in execution_table where fraction 0.6667 is taken to fill exactly to capacity.

Why do we sort items by value/weight ratio first?

Sorting ensures we pick items that give the most value per weight first, maximizing total value. This is shown in step 1 where items are sorted before selection.

What happens if the knapsack capacity is reached exactly after adding an item?

The algorithm stops adding more items, as shown in step 5 where totalWeight equals capacity and no further items are added.

Visual Quiz - 3 Questions

Look at the execution_table, what is the totalValue after step 3?

A 160

B 100

C 60

D 240

💡 Hint

Check the 'Total Value' column in execution_table row for step 3.

At which step does the knapsack reach full capacity?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at 'Total Weight' and 'Knapsack State' columns in execution_table.

If the capacity was 60 instead of 50, what would happen at step 4?

A Take full last item (fraction 1)

B Take no fraction (fraction 0)

C Take fraction 0.5

D Stop at step 3

💡 Hint

With more capacity, the whole last item can fit. Check fraction taken in execution_table step 4.

Concept Snapshot

Fractional Knapsack Problem:
- Sort items by value/weight ratio descending
- Add full items while capacity allows
- Add fraction of next item if needed
- Maximize total value within capacity
- Greedy approach works for fractional case

Full Transcript

The Fractional Knapsack Problem is solved by first sorting items by their value-to-weight ratio from highest to lowest. Then, starting with an empty knapsack, we add items fully if they fit. If the next item cannot fit fully, we add only the fraction that fits to fill the knapsack exactly. This process continues until the knapsack reaches its capacity. The total value is maximized by this greedy method. The execution table shows each step, the fraction taken, and the running totals of weight and value. Key points include why sorting is necessary, why fractions are taken, and when the process stops.

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