Fractional Knapsack Problem in DSA Typescript - Build from Scratch

Fractional Knapsack Problem

📖 Scenario: You are helping a delivery company pack valuable items into a knapsack. Each item has a weight and a value. The knapsack can carry a limited weight. To maximize profit, you can take fractions of items.

🎯 Goal: Build a program that calculates the maximum total value that fits into the knapsack by taking whole or fractional parts of items.

📋 What You'll Learn

Create an array of items with exact weights and values

Add a variable for the knapsack's maximum weight capacity

Implement the fractional knapsack logic to maximize total value

Print the maximum total value with two decimal places

💡 Why This Matters

🌍 Real World

This problem models packing cargo, loading trucks, or resource allocation where partial quantities can be chosen.

💼 Career

Understanding greedy algorithms like fractional knapsack is important for optimization tasks in software engineering and data science.

1

Create the items array

Create an array called items with these exact objects: { weight: 10, value: 60 }, { weight: 20, value: 100 }, { weight: 30, value: 120 }

DSA Typescript

// Your code here

Hint

Use an array of objects with weight and value properties.

2

Set the knapsack capacity

Create a variable called capacity and set it to 50

DSA Typescript

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

Hint

Use a simple number variable for the knapsack's weight limit.

3

Implement fractional knapsack logic

Write code to calculate the maximum total value by sorting items by value per weight, then taking whole or fractional parts until capacity is full. Store the result in a variable called maxValue

DSA Typescript

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

const capacity = 50;

// Your code here

Hint

Sort items by value/weight ratio descending. Use a loop to add full or fractional items until capacity is used.

4

Print the maximum total value

Print the variable maxValue rounded to two decimal places using console.log(maxValue.toFixed(2))

DSA Typescript

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

const capacity = 50;

items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));

let remainingCapacity = capacity;
let maxValue = 0;

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

// Your code here

Hint

Use console.log(maxValue.toFixed(2)) to print the result with two decimals.