0/1 Knapsack Problem

Dynamic Programming

https://leetcode.com/discuss/study-guide/1152328/01-Knapsack-Problem-and-Dynamic-Programming

Statement

You are given n items whose weights and values are known, as well as a knapsack to carry these items. The knapsack cannot carry more than a certain maximum weight, known as its capacity.

You need to maximize the total value of the items in your knapsack, while ensuring that the sum of the weights of the selected items does not exceed the capacity of the knapsack.

If there is no combination of weights whose sum is within the capacity constraint, return 0.

Constraints:

• 1≤1≤ capacity ≤104≤104

• 1≤1≤ values.length ≤103≤103

• weights.length ==== values.length

• 1≤1≤ values[i] ≤104≤104

• 1≤1≤ weights[i] ≤≤ capacity

export function findMaxKnapsackProfit(capacity, weights, values) {
    // Number of items  
    const n = weights.length;

    // Create a 2D array (dp) to store the maximum value achievable 
    // for each combination of items and capacity.
    // Initialize it with 0 for all cells.
    const dp = Array.from(Array(n + 1), () => Array(capacity + 1).fill(0));

    // Iterate over each item
    for (let i = 1; i <= n; i++) {
        // Itrate over each capacity value
        for (let j = 1; j <= capacity; j++) {
            // If the current item's weight is less than or equal to the current capacity
            if (weights[i - 1] <= j) {
                // Calculate the maximum value achievable by either including the current item
                // (values[i-1] + value of the remaining capacity after considering the current item)
                // or excluding the current item (maximum value achieved without considering the current item).
                // Choose the option with a higher value.
                dp[i][j] = Math.max(
                    // Including current item
                    values[i - 1] + dp[i - 1][j - weights[i - 1]],
                    // Excluding current item
                    dp[i - 1][j]
                );
            } 
            // If the current item's weight is greater than the current capacity
            else {
                // The maximum value achievable remains the same as the value achieved by excluding the current item.
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // Return the maximum value achievable for the given number of items and capacity.
    return dp[n][capacity];
}

Time Complexity O(n * capacity) The nested loops iterate over the number of items (n) and the capacity of the knapsack. Therefore, the time complexity is proportional to the product of these two values.

Space Complexity O(n * capacity) The space complexity is determined by the size of the dynamic programming array (dp), which has dimensions (n+1) x (capacity+1). Thus, the space required is proportional to the product of (n+1) and (capacity+1).

In both cases, the time and space complexity are polynomial in terms of the number of items and the capacity of the knapsack. This is efficient and practical for typical problem sizes. However, it's worth noting that if the values of n and capacity become very large, the solution may require significant memory and time resources.