Fractional Knapsack Problem in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fractional Knapsack Calculation

What is the output of the following JavaScript code that calculates the maximum value for the fractional knapsack problem?

DSA Javascript

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

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

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

A "240.00"

B "220.00"

C "180.00"

D "200.00"

💡 Hint

Sort items by value per weight and take as much as possible from the highest ratio first.

The function sorts items by value per weight descending. It takes full 10 weight of first item (value 60), full 20 weight of second (value 100), and 20 weight of third (partial, value 80). Total value = 60 + 100 + 80 = 240.

🧠 Conceptual

intermediate

Key Idea Behind Fractional Knapsack

Which statement best describes the key idea behind the fractional knapsack problem?

A You sort items by weight and pick the lightest first.

B You can take fractions of items to maximize total value within capacity.

C You must take whole items only, no fractions allowed.

D You pick items randomly until capacity is full.

💡 Hint

Fractional knapsack allows partial items, unlike 0/1 knapsack.

The fractional knapsack problem allows taking any fraction of an item to maximize value within the capacity limit.

❓ Predict Output

advanced

Output with Different Capacity

What is the output of this code when the knapsack capacity is 40?

DSA Javascript

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

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

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

A "200.00"

B "240.00"

C "180.00"

D "220.00"

💡 Hint

Take full items with highest value/weight ratio until capacity is reached.

Take full 10 weight of first item (60), full 20 weight of second (100), and 10 weight of third (40 value). Total = 60 + 100 + 40 = 200.

🔧 Debug

advanced

Identify the Error in Fractional Knapsack Code

What error will this code produce when run?

DSA Javascript

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

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

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

A SyntaxError due to missing semicolon

B ReferenceError due to wrong function call

C No error, outputs "240.00"

D TypeError because of undefined variable

💡 Hint

JavaScript allows missing semicolons in many cases.

JavaScript does not require semicolons at the end of statements; the code runs fine and outputs 240.00.

🧠 Conceptual

expert

Why Greedy Works for Fractional Knapsack but Not 0/1 Knapsack

Why does the greedy approach guarantee an optimal solution for the fractional knapsack problem but not for the 0/1 knapsack problem?

A Because 0/1 knapsack has fewer items to choose from.

B Because fractional knapsack ignores item weights.

C Because greedy algorithms always work for all knapsack problems.

D Because fractional knapsack allows taking parts of items, so sorting by value/weight ratio always leads to optimal value.

💡 Hint

Think about how partial items affect the solution space.

Fractional knapsack allows splitting items, so taking the highest value/weight ratio first always leads to the best total value. 0/1 knapsack requires whole items, so greedy can miss better combinations.

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