Fractional Knapsack Problem in DSA Javascript - 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 whole item fit?

No→Take fraction to fill knapsack

|Yes↓

Add full item weight and value

↓

Update total weight and value

↓

Knapsack full?

No→Next item

|Yes↓

Done

The algorithm sorts items by value per weight, then adds full or fractional items until the knapsack is full.

Execution Sample

DSA Javascript

const items = [{value: 60, weight: 10}, {value: 100, weight: 20}, {value: 120, weight: 30}];
const capacity = 50;
// Sort by value/weight ratio
// Add items fully or fractionally
// Calculate total value

This code sorts items by value per weight and fills the knapsack to maximize total value.

Execution Table

Step	Operation	Item (value, weight)	Weight Added	Value Added	Total Weight	Total Value	Knapsack State
1	Sort items by value/weight ratio	[(60,10), (100,20), (120,30)]	0	0	0	0	[]
2	Consider item 1	(60,10)	10	60	10	60	[(60,10)]
3	Consider item 2	(100,20)	20	100	30	160	[(60,10), (100,20)]
4	Consider item 3	(120,30)	20 (fraction)	80 (fraction)	50	240	[(60,10), (100,20), (120,20)]
5	Knapsack full	N/A	0	0	50	240	Final state

💡 Knapsack capacity reached at total weight 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
knapsackItems	[]	[(60,10)]	[(60,10),(100,20)]	[(60,10),(100,20),(120,20)]	[(60,10),(100,20),(120,20)]

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. The execution_table row 4 shows we add only 20 weight units (fraction) to fill the knapsack exactly.

How do we decide the order of items to add?

We sort items by their value-to-weight ratio before adding. Step 1 in the execution_table shows the sorted order ensures maximum value gain per weight.

What happens if the knapsack capacity is larger than total item weight?

The algorithm adds all items fully without fractions. The knapsack fills before fractions are needed, as shown by the absence of fractional addition in steps.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, how much weight of the last item is added?

A 30 units

B 10 units

C 20 units

D 0 units

💡 Hint

Check the 'Weight Added' column at step 4 in the execution_table.

At which step does the knapsack reach full capacity?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Total Weight' column and the 'Knapsack full' note in the execution_table.

If the capacity was 60 instead of 50, what would change in the execution_table?

A The last item would be added fully with 30 weight units

B The last item would still be added fractionally with 20 weight units

C The first item would be added fractionally

D No items would be added

💡 Hint

Consider the total weights of items and the capacity in the variable_tracker.

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 in knapsack
- Greedy approach, runs in O(n log n) due to sorting

Full Transcript

The Fractional Knapsack Problem is solved by sorting items based on their value-to-weight ratio. We then add items fully to the knapsack until we cannot add a whole item without exceeding capacity. At that point, we add only the fraction of the item that fits. This approach ensures the maximum total value is achieved. The execution table shows each step: sorting, adding full items, adding a fractional item, and stopping when the knapsack is full. Variables track total weight, total value, and items included. Key moments clarify why fractions are needed and how sorting affects the solution. The visual quiz tests understanding of these steps.

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. Maximize total weight without considering value

C. Select only whole items to maximize value

D. Minimize the number of items selected

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Compare options

   Maximize total value by taking fractions of items within weight limit correctly states maximizing value by taking fractions. Others ignore fractions or value maximization.

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: fractions allowed to maximize value [OK]

Common Mistakes:

• Thinking only whole items can be taken
• Ignoring value and focusing on weight
• Confusing with 0/1 knapsack problem

2. Which of the following JavaScript code snippets correctly sorts items by value-to-weight ratio for the fractional knapsack?

easy

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

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

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

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

Solution

1. Step 1: Identify sorting criteria

   We must sort items by descending value-to-weight ratio (value/weight) to pick best items first.

2. Step 2: Check each code snippet

   items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight)); sorts descending by (value/weight). Others sort incorrectly by inverse or by value or weight alone.

3. Final Answer:

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

4. Quick Check:

   Sort by descending value/weight ratio [OK]

Hint: Sort items by (value/weight) descending [OK]

Common Mistakes:

• Sorting by weight or value alone
• Sorting ascending instead of descending
• Using inverse ratio (weight/value)

3. What is the output of the following JavaScript code?

const items = [
  {value: 60, weight: 10},
  {value: 100, weight: 20},
  {value: 120, weight: 30}
];
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. 220

B. 240

C. 180

D. 200

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 fraction of item3: (20/30)*120 = 80.
   Total value = 60 + 100 + 80 = 240.

3. Final Answer:

   240 -> Option B

4. Quick Check:

   Sum values with fractions = 240 [OK]

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

Common Mistakes:

• Not sorting by ratio correctly
• Taking items without fractions
• Miscomputing fraction value

4. Find the error in this fractional knapsack code snippet:

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. Incorrect fraction calculation formula

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

C. Missing return statement

D. Sorting is ascending; should be descending by value/weight ratio

Solution

1. Step 1: Analyze sorting order

   The code sorts items ascending by value/weight ratio, but we need descending to pick best items first.

2. Step 2: Check other parts

   Return statement exists, fraction formula is correct, 'let' is appropriate for totalValue.

3. Final Answer:

   Sorting is ascending; should be descending by value/weight ratio -> Option D

4. Quick Check:

   Sort descending by ratio to maximize value [OK]

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

Common Mistakes:

• Sorting ascending instead of descending
• Ignoring fraction calculation correctness
• Confusing variable declarations

5. Given items with values and weights:

items = [
  {value: 40, weight: 2},
  {value: 100, weight: 20},
  {value: 50, weight: 10},
  {value: 60, weight: 12}
];
capacity = 30;

What is the maximum total value achievable using the fractional knapsack approach?

hard

A. 190

B. 160

C. 180

D. 200

Solution

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

   Ratios:
   Item1: 40/2=20
   Item2: 100/20=5
   Item3: 50/10=5
   Item4: 60/12=5
   Sorted order: Item1, then Items 2,3,4 (equal ratio 5).

2. Step 2: Pick items until capacity 30

   Take Item1 fully: weight 2, value 40, remaining 28.
   Next, take Item2 fully: weight 20, value 100, remaining 8.
   Then take fraction of Item3: fraction = 8/10 = 0.8, value = 50 * 0.8 = 40.
   Total value = 40 + 100 + 40 = 180.

3. Step 3: Check if taking Item4 fraction is better

   Item4 has same ratio as Item3, but we already used remaining capacity on Item3 fraction.
   So total value remains 180.

4. Final Answer:

   180 -> Option C

5. Quick Check:

   Sum values with fractions = 180 [OK]

Hint: Pick highest ratio items first, then fractions [OK]

Common Mistakes:

• Ignoring highest ratio item first
• Not taking fractions correctly
• Adding values without considering capacity