knapsack-test.js

/**
 * Problem: 0/1 Knapsack
 *
 * You are given two arrays:
 * - weights[i] = weight of the i-th item
 * - values[i] = value of the i-th item
 *
 * And an integer `capacity` representing the max weight the knapsack can hold.
 *
 * Goal:
 * Return the **maximum total value** you can carry without exceeding the capacity.
 *
 * You may either **take or skip** each item — but not take it more than once (0/1).
 */

function knapsack(weights, values, capacity) {
    // 1. Initialize dp table with (n + 1) x (capacity + 1) filled with 0
    // 2. Loop through each item (i = 1 to n)
    //    a. For each capacity (w = 0 to capacity):
    //       - If current item's weight > w → skip (inherit dp[i-1][w])
    //       - Else:
    //         dp[i][w] = max of:
    //            - not taking the item: dp[i-1][w]
    //            - taking the item: dp[i-1][w - weight] + value
    // 3. Return dp[n][capacity] → max value with all items and full capacity
}

function testKnapsack() {
    const weights = [1, 3, 4, 5];
    const values = [1, 4, 5, 7];
    const capacity = 7;

    const expected = 9; // take items with weight 3 (val 4) and 4 (val 5)
    const actual = knapsack(weights, values, capacity);

    console.log(actual === expected ? "✅ PASS" : `❌ FAIL (got ${actual}, expected ${expected})`);
}

testKnapsack();