0 1 Knapsack Problem in DSA Typescript - Build from Scratch

0 1 Knapsack Problem

📖 Scenario: You are packing a backpack for a hiking trip. You have a list of items, each with a weight and a value. Your backpack can only carry a limited weight. You want to choose items to maximize the total value without exceeding the weight limit.

🎯 Goal: Build a program that uses the 0 1 Knapsack algorithm to find the maximum value of items you can carry without exceeding the backpack's weight limit.

📋 What You'll Learn

Create an array of items with exact weights and values

Create a variable for the maximum weight capacity

Implement the 0 1 Knapsack dynamic programming solution

Print the maximum value that fits in the backpack

💡 Why This Matters

🌍 Real World

Packing efficiently for trips, resource allocation, budget planning, and many optimization problems use the 0 1 Knapsack approach.

💼 Career

Understanding dynamic programming and optimization algorithms is valuable for software engineering roles, especially in fields like logistics, finance, and game development.

1

Create the items array

Create a constant array called items with these exact objects: { weight: 2, value: 3 }, { weight: 3, value: 4 }, { weight: 4, value: 5 }, { weight: 5, value: 8 }

DSA Typescript

// Your code here

Hint

Use an array of objects with weight and value properties.

2

Set the maximum weight capacity

Create a constant called maxWeight and set it to 5

DSA Typescript

const items = [
  { weight: 2, value: 3 },
  { weight: 3, value: 4 },
  { weight: 4, value: 5 },
  { weight: 5, value: 8 }
];
// Your code here

Hint

This is the weight limit your backpack can carry.

3

Implement the 0 1 Knapsack algorithm

Create a function called knapsack that takes items and maxWeight as parameters and returns the maximum value. Use a 2D array dp where dp[i][w] stores the max value using first i items with weight limit w. Fill dp using nested for loops over items and weights. Return dp[items.length][maxWeight].

DSA Typescript

const items = [
  { weight: 2, value: 3 },
  { weight: 3, value: 4 },
  { weight: 4, value: 5 },
  { weight: 5, value: 8 }
];

const maxWeight = 5;

// Your code here

Hint

Use dynamic programming with a 2D array to store max values for subproblems.

4

Print the maximum value

Call the knapsack function with items and maxWeight and print the result using console.log.

DSA Typescript

const items = [
  { weight: 2, value: 3 },
  { weight: 3, value: 4 },
  { weight: 4, value: 5 },
  { weight: 5, value: 8 }
];

const maxWeight = 5;

function knapsack(items: { weight: number; value: number }[], maxWeight: number): number {
  const n = items.length;
  const dp: number[][] = Array.from({ length: n + 1 }, () => Array(maxWeight + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    const { weight, value } = items[i - 1];
    for (let w = 0; w <= maxWeight; w++) {
      if (weight <= w) {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weight] + value);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }

  return dp[n][maxWeight];
}

// Your code here

Hint

The maximum value that fits in the backpack with weight limit 5 is 8.