The Knapsack Problem involves selecting a subset of items from a given set, each with a weight and a value, to maximize the total value while not exceeding a predefined weight limit. It is a challenging combinatorial optimization problem with various real-world applications.

There are two main variations of the Knapsack Problem: the 0/1 Knapsack Problem, where items cannot be broken into smaller pieces, and the Fractional Knapsack Problem, where items can be divided to fill the knapsack optimally.

function knapsack01(values, weights, capacity) {
    const n = values.length;
    const dp = Array.from(
        { length: n + 1 }, () => Array(capacity + 1).fill(0)
    );
    
    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                    dp[i - 1][w], 
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}

// Example usage:
const values = [120, 60, 100];
const weights = [30, 10, 20];
const capacity = 50;
console.log("Maximum value:", knapsack01(values, weights, capacity)); // Output: 220

The time complexity of the 0/1 Knapsack dynamic programming solution is O(n * W), where n is the number of items and W is the maximum capacity of the knapsack.

The Knapsack Problem finds applications in various fields such as resource allocation in project management, portfolio optimization in finance, and resource management in logistics.