0/1 Knapsack Problem

The 0/1 Knapsack Problem is a classic optimization problem in computer science and combinatorial optimization.

In this problem, you are given a set of items, each with a weight and a value, and you need to determine the combination of items to include in a knapsack with a maximum capacity (weight limit) without exceeding it, while maximizing the total value of the items included.

pseudocode:

function knapsack(weights[], values[], capacity, n):
    // Initialize a table to store the maximum value that can be achieved
    // for each weight from 0 to capacity for items 0 to n
    table[n+1][capacity+1]

    // Initialize the table with zeros
    for i from 0 to n:
        table[i][0] = 0
    for j from 0 to capacity:
        table[0][j] = 0

    // Build the table using dynamic programming
    for i from 1 to n:
        for j from 1 to capacity:
            if weights[i-1] > j:
                // If the current item's weight is more than the capacity,
                // we cannot include it in the knapsack
                table[i][j] = table[i-1][j]
            else:
                // Otherwise, we consider whether to include the item or not
                // by comparing the value of including the item with the value
                // of not including it
                table[i][j] = max(values[i-1] + table[i-1][j-weights[i-1]], table[i-1][j])

    // The result is stored in the bottom-right cell of the table
    return table[n][capacity]

function knapsack(capacity, weights, values, n) {
    let dp = Array(n + 1).fill(0).map(() => Array(capacity + 1).fill(0));

    for (let i = 0; i <= n; i++) {
        for (let w = 0; w <= capacity; w++) {
            if (i === 0 || w === 0) {
                dp[i][w] = 0;
            } else if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    let selectedItems = [];
    let i = n, w = capacity;
    while (i > 0 && w > 0) {
        if (dp[i][w] !== dp[i - 1][w]) {
            selectedItems.push(i - 1);
            w -= weights[i - 1];
        }
        i--;
    }

    return {
        maxValue: dp[n][capacity],
        selectedItems: selectedItems.reverse()
    };
}

// Example usage:
const capacity = 10;
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const n = weights.length;
const result = knapsack(capacity, weights, values, n);
console.log("Max Value:", result.maxValue);
console.log("Selected Items:", result.selectedItems.map(item => `Item ${item + 1}`));

In this example:

• capacity is the maximum weight that the knapsack can hold.

• weights is an array containing the weights of each item.

• values is an array containing the values of each item.

• n is the number of items.

• The knapsack function calculates the maximum value that can be obtained and returns an object containing the maximum value and the indices of the selected items.