Fractional Knapsack Problem in DSA Typescript - Deep Dive

Overview - Fractional Knapsack Problem

What is it?

The Fractional Knapsack Problem is a way to choose items with weights and values to put into a bag with limited capacity. Unlike the 0/1 knapsack, you can take fractions of items, not just whole ones. The goal is to maximize the total value in the bag without exceeding its weight limit. This problem helps us understand how to make the best choices when resources are limited.

Why it matters

This problem exists because in real life, sometimes you can take parts of things, like cutting a rope or pouring some liquid, to fit your needs best. Without this idea, we would waste resources or miss chances to get the most value. It teaches us how to make smart decisions quickly when we can't carry everything.

Where it fits

Before learning this, you should understand basic arrays, sorting, and greedy algorithms. After this, you can explore the 0/1 Knapsack Problem, dynamic programming, and optimization techniques.

Mental Model

Core Idea

Pick items by their value per weight, taking as much as possible from the best ratio until the bag is full.

Think of it like...

Imagine filling a jar with different types of honey, each with a different sweetness per spoonful. You want the sweetest jar, so you first add the honey with the highest sweetness per spoon, then the next best, and so on, even if you only have space for part of a spoon.

Bag capacity: 50
Items sorted by value/weight:
┌─────────────┬─────────────┬─────────────┐
│ Item        │ Weight      │ Value       │
├─────────────┼─────────────┼─────────────┤
│ Item A      │ 10          │ 60          │
│ Item B      │ 20          │ 100         │
│ Item C      │ 30          │ 120         │
└─────────────┴─────────────┴─────────────┘
Fill order by value/weight:
Item A (6), Item B (5), Item C (4)
Fill bag: take all of A (10), all of B (20), then 20 of C (partial) to fill 50 capacity.

Build-Up - 6 Steps

1

Foundation

Understanding the Problem Setup

Concept: Learn what the knapsack problem is and how fractional items differ from whole items.

You have a bag that can hold a certain weight. You have items, each with a weight and a value. You want to fill the bag to get the highest total value. Unlike some problems, you can take parts of items, not just whole ones.

Result

You know the problem allows splitting items and aims to maximize value within weight limits.

Understanding the ability to take fractions changes the problem from complex to solvable by simple rules.

2

Foundation

Calculating Value per Weight Ratio

Concept: Each item's value per unit weight guides which to pick first.

For each item, divide its value by its weight to get value per weight. This tells you how valuable each unit of weight is for that item. For example, an item worth 60 with weight 10 has a ratio of 6.

Result

You have a list of items with their value/weight ratios calculated.

Knowing this ratio lets you compare items fairly regardless of size.

3

Intermediate

Sorting Items by Value Density

🤔Before reading on: do you think sorting items by value per weight helps pick the best items first? Commit to yes or no.

Concept: Sort items from highest to lowest value per weight to prioritize picking.

Sort the list of items so the one with the highest value per weight comes first. This way, you always pick the most valuable weight units first, ensuring maximum total value.

Result

Items are ordered to pick the best fractions first.

Sorting by value density is the key greedy step that guarantees optimal fractional knapsack solution.

4

Intermediate

Greedy Selection of Items

🤔Before reading on: do you think taking whole items first or fractions first leads to better total value? Commit to your answer.

Concept: Pick items in order, taking whole items if possible, or fractions if not, until the bag is full.

Start with the first item in the sorted list. If it fits entirely, take it all and reduce the bag capacity. If not, take the fraction that fits and stop. Repeat until the bag is full or no items remain.

Result

You get the maximum total value possible by taking whole or fractional items.

Greedy picking based on sorted ratios ensures the best use of limited capacity.

5

Advanced

Implementing Fractional Knapsack in TypeScript

🤔Before reading on: do you think a simple loop with sorting and fraction calculation can solve this? Commit to yes or no.

Concept: Write code that sorts items and picks fractions to maximize value.

interface Item { value: number; weight: number; } function fractionalKnapsack(items: Item[], capacity: number): number { // Calculate value per weight items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight)); let totalValue = 0; let remainingCapacity = capacity; for (const item of items) { if (remainingCapacity === 0) break; if (item.weight <= remainingCapacity) { totalValue += item.value; remainingCapacity -= item.weight; } else { const fraction = remainingCapacity / item.weight; totalValue += item.value * fraction; remainingCapacity = 0; } } return totalValue; } // Example usage: const items = [ { value: 60, weight: 10 }, { value: 100, weight: 20 }, { value: 120, weight: 30 } ]; const capacity = 50; console.log(fractionalKnapsack(items, capacity));

Result

Output: 240 Explanation: Takes all of item A (60), all of item B (100), and 2/3 of item C (80) for total 240.

Implementing the algorithm solidifies understanding of sorting and greedy selection in practice.

6

Expert

Why Fractional Knapsack is Greedy Optimal

🤔Before reading on: do you think greedy always works for knapsack problems? Commit to yes or no.

Concept: Understand why greedy choice leads to the best solution only when fractions are allowed.

Because you can take fractions, picking the item with the highest value per weight first always improves or maintains the total value. If you tried to pick a lower ratio item first, you would lose potential value. This property does not hold if you must take whole items only.

Result

Greedy algorithm guarantees the maximum total value for fractional knapsack.

Knowing why greedy works here prevents confusion when it fails in 0/1 knapsack and guides algorithm choice.

Under the Hood

The algorithm sorts items by their value-to-weight ratio. Then it iterates through the sorted list, adding whole items if possible or fractions if not, updating the remaining capacity and total value. This works because the problem has the greedy-choice property and optimal substructure, meaning local optimal choices lead to global optimum.

Why designed this way?

The fractional knapsack problem was designed to model situations where partial items can be taken, making it solvable by a greedy approach. This contrasts with the 0/1 knapsack, which is NP-hard and requires dynamic programming. The design leverages the continuous nature of fractions to simplify the problem.

Items sorted by value/weight:
[Item1] -> [Item2] -> [Item3] -> ...

Start with capacity C

For each item:
  ┌─────────────┐
  │ Check weight │
  └─────┬───────┘
        │
  Fits? ├─Yes─> Take whole item, reduce capacity
        │
        No
        │
  Take fraction to fill capacity
        ↓
  End

Myth Busters - 4 Common Misconceptions

Quick: Does greedy always work for all knapsack problems? Commit yes or no.

Common Belief: Greedy approach always gives the best solution for any knapsack problem.

Reality: Greedy works only for fractional knapsack, not for 0/1 knapsack where items can't be split.

Why it matters: Using greedy for 0/1 knapsack leads to wrong answers and wasted effort.

Quick: Can you take more than the bag capacity by splitting items? Commit yes or no.

Common Belief: You can take fractions that exceed the bag's capacity if it increases value.

Reality: The total weight taken, including fractions, must never exceed the bag's capacity.

Why it matters: Ignoring capacity constraints breaks the problem rules and produces invalid solutions.

Quick: Is sorting items by value alone enough? Commit yes or no.

Common Belief: Sorting items by their total value is enough to maximize the knapsack value.

Reality: Sorting must be by value per weight, not total value, to maximize value within weight limits.

Why it matters: Sorting by total value can cause picking heavy low-value-density items first, reducing total value.

Quick: Does fractional knapsack always require complex dynamic programming? Commit yes or no.

Common Belief: Fractional knapsack needs dynamic programming like 0/1 knapsack.

Reality: Fractional knapsack can be solved optimally with a simple greedy algorithm.

Why it matters: Misunderstanding this leads to overcomplicated solutions and wasted time.

Expert Zone

1

The fractional knapsack problem's greedy solution relies on the problem's continuous nature; even tiny fractions can be taken to fill capacity exactly.

2

In practice, floating-point precision can affect fraction calculations, so careful handling is needed in implementations.

3

The problem can be extended to multiple knapsacks or additional constraints, where greedy no longer guarantees optimality.

When NOT to use

Do not use fractional knapsack greedy approach when items cannot be split (0/1 knapsack) or when additional constraints like item dependencies exist. Instead, use dynamic programming or branch-and-bound methods.

Production Patterns

Fractional knapsack is used in resource allocation problems like bandwidth distribution, cutting raw materials, or portfolio optimization where divisible resources maximize returns.

Connections

0/1 Knapsack Problem

Related problem with similar setup but no fractional items allowed.

Understanding fractional knapsack helps grasp why 0/1 knapsack is harder and requires different algorithms.

Greedy Algorithms

Fractional knapsack is a classic example of a greedy algorithm application.

Knowing this problem deepens understanding of when greedy algorithms work optimally.

Resource Allocation in Economics

Fractional knapsack models how to allocate limited resources to maximize profit or utility.

Seeing this connection shows how computer science algorithms apply to economic decision-making.

Common Pitfalls

#1 Taking items without sorting by value per weight.

Wrong approach:

function fractionalKnapsack(items, capacity) {
let totalValue = 0;
let remaining = capacity;
for (const item of items) {
if (item.weight <= remaining) {
totalValue += item.value;
remaining -= item.weight;
} else {
const fraction = remaining / item.weight;
totalValue += item.value * fraction;
break;
}
}
return totalValue;
}

Correct approach:

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 {
const fraction = remaining / item.weight;
totalValue += item.value * fraction;
break;
}
}
return totalValue;
}

Root cause:

Not sorting items by value density ignores the greedy principle, leading to suboptimal total value.

#2 Allowing total weight to exceed capacity by taking too large fractions.

Wrong approach:

const fraction = 1; // always take whole item without checking capacity
if (item.weight <= remaining) {
totalValue += item.value;
remaining -= item.weight;
} else {
totalValue += item.value; // wrong: adding full value without fraction
remaining -= item.weight; // negative capacity possible
}

Correct approach:

const fraction = remaining / item.weight;
totalValue += item.value * fraction;
remaining = 0;

Root cause:

Ignoring capacity constraints when taking fractions causes invalid solutions.

#3 Using integer division or rounding fractions incorrectly.

Wrong approach:

const fraction = Math.floor(remaining / item.weight); // rounds down to 0 or 1
// leads to taking no fraction when some fraction is possible

Correct approach:

const fraction = remaining / item.weight; // use floating-point division for accurate fraction

Root cause:

Misunderstanding fraction calculation leads to losing possible value.

Key Takeaways

Fractional Knapsack allows taking parts of items to maximize value within weight limits.

Sorting items by value per weight ratio is essential for the greedy solution.

Greedy algorithm works optimally here because of the problem's continuous nature.

This problem contrasts with 0/1 knapsack, which requires more complex methods.

Understanding fractional knapsack deepens insight into resource allocation and greedy algorithms.

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