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.