Unbounded Knapsack Problem in DSA Typescript - Build from Scratch

Unbounded Knapsack Problem

📖 Scenario: You are helping a shop owner decide how to fill a knapsack with items to maximize value. The knapsack can hold a limited weight, and the owner can use unlimited quantities of each item.

🎯 Goal: Build a program that calculates the maximum value achievable with unlimited items given their weights and values and the knapsack's capacity.

📋 What You'll Learn

Create arrays for item weights and values with exact values

Create a variable for knapsack capacity with exact value

Implement the unbounded knapsack dynamic programming logic

Print the maximum value achievable

💡 Why This Matters

🌍 Real World

This problem helps in resource allocation where you can use unlimited quantities of items, like packing goods or budgeting.

💼 Career

Understanding dynamic programming and knapsack problems is important for software engineers working on optimization, logistics, and algorithm design.

1

Create item weights and values arrays

Create an array called weights with values [2, 3, 4, 5] and an array called values with values [3, 4, 5, 6].

DSA Typescript

# Your code here

Hint

Use const weights = [2, 3, 4, 5]; and const values = [3, 4, 5, 6];

2

Create knapsack capacity variable

Create a variable called capacity and set it to 8.

DSA Typescript

const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
# Your code here

Hint

Use const capacity = 8; to set the knapsack capacity.

3

Implement unbounded knapsack logic

Create an array called dp of length capacity + 1 filled with zeros. Use a for loop with variable w from 1 to capacity. Inside it, use another for loop with variable i from 0 to weights.length - 1. If weights[i] is less than or equal to w, update dp[w] to the maximum of dp[w] and dp[w - weights[i]] + values[i].

DSA Typescript

const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 8;
# Your code here

Hint

Use two nested loops and update dp[w] with the maximum value possible.

4

Print the maximum value achievable

Print the value of dp[capacity] using console.log(dp[capacity]).

DSA Typescript

const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 8;

const dp = new Array(capacity + 1).fill(0);
for (let w = 1; w <= capacity; w++) {
    for (let i = 0; i < weights.length; i++) {
        if (weights[i] <= w) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
}
# Your code here

Hint

Use console.log(dp[capacity]) to print the maximum value.