Fractional Knapsack Problem in DSA Javascript

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 perfectly.

Items: [value/weight]
[60/10] -> [100/20] -> [120/30] -> null
Knapsack capacity: 50 units
Goal: maximize total value inside knapsack

Dry Run Walkthrough

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

Goal: Fill knapsack with maximum value, allowing fractional parts of items

Step 1: Calculate value per weight for each item and sort items by this ratio descending

[60/10=6] -> [100/20=5] -> [120/30=4] sorted as 60/10 -> 100/20 -> 120/30

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

Step 2: Take full first item (weight 10, value 60) into knapsack

Knapsack: 10/50 filled, total value=60

Why: We can take full item because it fits entirely

Step 3: Take full second item (weight 20, value 100) into knapsack

Knapsack: 30/50 filled, total value=160

Why: Still enough capacity to take full second item

Step 4: Take fraction of third item to fill remaining capacity (20/30 of item, value fraction 80)

Knapsack: 50/50 filled, total value=240

Why: Only 20 units capacity left, so take fraction of last item to maximize value

Result:

Knapsack full: total value = 240

Annotated Code

DSA Javascript

class Item {
  constructor(value, weight) {
    this.value = value;
    this.weight = weight;
    this.ratio = value / weight;
  }
}

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

  let totalValue = 0;
  let remainingCapacity = capacity;

  for (const item of items) {
    if (remainingCapacity === 0) break; // knapsack full

    if (item.weight <= remainingCapacity) {
      // take full item
      totalValue += item.value;
      remainingCapacity -= item.weight;
    } else {
      // take fraction of item
      const fraction = remainingCapacity / item.weight;
      totalValue += item.value * fraction;
      remainingCapacity = 0; // knapsack 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.ratio - a.ratio);

sort items by value per weight descending to prioritize best value

if (remainingCapacity === 0) break;

stop if knapsack is full

if (item.weight <= remainingCapacity) { totalValue += item.value; remainingCapacity -= item.weight; }

take full item if it fits

else { const fraction = remainingCapacity / item.weight; totalValue += item.value * fraction; remainingCapacity = 0; }

take fraction of item to fill remaining capacity

Output

240.00

Complexity Analysis

Time: O(n log n) because we sort n items by value/weight ratio

Space: O(n) for storing items and their ratios

vs Alternative: Better than trying all combinations (which is exponential), fractional knapsack uses greedy sorting for efficient solution

Edge Cases

empty items list

returns 0 value because no items to take

DSA Javascript

for (const item of items) { if (remainingCapacity === 0) break; ... }

knapsack capacity zero

returns 0 value immediately

DSA Javascript

if (remainingCapacity === 0) break;

items with zero weight

division by zero avoided by ratio calculation; if zero weight, handle separately or ignore

DSA Javascript

this.ratio = value / weight; (should ensure weight > 0 in input)

When to Use This Pattern

When you need to maximize value with divisible items and limited capacity, use the fractional knapsack greedy approach by sorting items by value per weight.

Common Mistakes

Mistake: Trying to take items in input order without sorting by value/weight ratio
Fix: Sort items by value/weight ratio descending before picking

Mistake: Not handling fractional part when remaining capacity is less than item weight
Fix: Calculate fraction and add proportional value for partial item

Summary

It finds the maximum total value by taking whole or fractional parts of items to fill a knapsack.

Use it when items can be divided and you want the best value for limited capacity.

The key is to pick items with the highest value per weight first, taking fractions if needed.

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