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.