Fractional Knapsack Problem in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fractional Knapsack Value Calculation

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

DSA Typescript

interface Item {
  value: number;
  weight: number;
}

function fractionalKnapsack(items: Item[], capacity: number): number {
  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
  let totalValue = 0;
  let remainingCapacity = capacity;

  for (const item of items) {
    if (item.weight <= remainingCapacity) {
      totalValue += item.value;
      remainingCapacity -= item.weight;
    } else {
      totalValue += item.value * (remainingCapacity / item.weight);
      break;
    }
  }
  return totalValue;
}

const items = [
  { value: 60, weight: 10 },
  { value: 100, weight: 20 },
  { value: 120, weight: 30 }
];
const capacity = 50;
console.log(fractionalKnapsack(items, capacity));

A 220

B 180

C 200

D 240

💡 Hint

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

The items are sorted by value/weight ratio: (60/10=6), (100/20=5), (120/30=4). We take all of the first item (value 60), all of the second (value 100), and 2/3 of the third (value 120 * 20/30 = 80). Total = 60 + 100 + 80 = 240.

🧠 Conceptual

intermediate

Understanding Fractional Knapsack Greedy Choice

Why does the fractional knapsack problem use a greedy approach based on value-to-weight ratio?

A Because taking items with the highest value-to-weight ratio first maximizes total value for the given capacity.

B Because it tries all combinations of items to find the best solution.

C Because it sorts items by weight only to minimize total weight.

D Because it selects items randomly to fill the knapsack quickly.

💡 Hint

Think about which items give the most value per unit weight.

The greedy approach picks items with the highest value per weight first to maximize the total value within the capacity. This works optimally for fractional knapsack because fractions of items can be taken.

🔧 Debug

advanced

Identify the Error in Fractional Knapsack Implementation

What error will the following TypeScript code produce when run?

DSA Typescript

interface Item {
  value: number;
  weight: number;
}

function fractionalKnapsack(items: Item[], capacity: number): number {
  items.sort((a, b) => (a.value / a.weight) - (b.value / b.weight));
  let totalValue = 0;
  let remainingCapacity = capacity;

  for (const item of items) {
    if (item.weight <= remainingCapacity) {
      totalValue += item.value;
      remainingCapacity -= item.weight;
    } else {
      totalValue += item.value * (remainingCapacity / item.weight);
      break;
    }
  }
  return totalValue;
}

const items = [
  { value: 60, weight: 10 },
  { value: 100, weight: 20 },
  { value: 120, weight: 30 }
];
const capacity = 50;
console.log(fractionalKnapsack(items, capacity));

A Outputs 240

B 220

C Throws a runtime error due to division by zero

D Outputs 200

💡 Hint

Check the sorting order and how it affects the selection of items.

The code sorts items in ascending order of value-to-weight ratio, so it picks the lowest ratio items first, resulting in a total value of 220 instead of the maximum 240.

📝 Syntax

advanced

Syntax Error in Fractional Knapsack Code

Which option contains a syntax error that will prevent the TypeScript code from compiling?

DSA Typescript

interface Item {
  value: number;
  weight: number;
}

function fractionalKnapsack(items: Item[], capacity: number): number {
  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
  let totalValue = 0;
  let remainingCapacity = capacity;

  for (const item of items) {
    if (item.weight <= remainingCapacity) {
      totalValue += item.value;
      remainingCapacity -= item.weight;
    } else {
      totalValue += item.value * (remainingCapacity / item.weight);
      break;
    }
  }
  return totalValue;
}

A Incorrect interface declaration for Item

B Wrong parameter types in fractionalKnapsack function

C Missing semicolon after totalValue += item.value * (remainingCapacity / item.weight)

D Using 'let' instead of 'const' for totalValue

💡 Hint

Look carefully at the line inside the else block.

The line 'totalValue += item.value * (remainingCapacity / item.weight)' is missing a semicolon at the end, causing a syntax error.

🚀 Application

expert

Maximum Value with Fractional Knapsack for Custom Items

Given the following items and knapsack capacity, what is the maximum value the fractional knapsack algorithm will return?

DSA Typescript

interface Item {
  value: number;
  weight: number;
}

const items: Item[] = [
  { value: 500, weight: 30 },
  { value: 400, weight: 20 },
  { value: 300, weight: 10 },
  { value: 450, weight: 25 }
];
const capacity = 50;

A 1060

B 950

C 850

D 1150

💡 Hint

Calculate value-to-weight ratios and take items starting from the highest ratio until capacity is full.

Ratios: 500/30 ≈ 16.67, 400/20 = 20, 300/10 = 30, 450/25 = 18. Taking item with ratio 30 fully (weight 10, value 300), then ratio 20 fully (weight 20, value 400), then ratio 18 partially (remaining capacity 20, item weight 25, fraction 20/25 = 0.8, value 450*0.8=360). Total = 300 + 400 + 360 = 1060.

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