0/1 Knapsack Maximum Profit

Given the weights and profits of $N$ items, we need to place these items into a knapsack with capacity $C$. The objective is to maximize the total profit of the items in the knapsack. Each item can be selected at most once.

Example:

Items: Item 1, Item 2, Item 3, Item 4
Individual Weights: 2, 3, 1, 4
Individual Profits: 4, 5, 3, 7
Knapsack Capacity: 5

Solution Approach

::: code-tabs
@tab Java

class Knapsack {
  public int solveKnapsack(int[] profits, int[] weights, int capacity) {
    // Base case validation
    if (capacity <= 0 || profits.length == 0 || weights.length != profits.length)
      return 0;
    int n = profits.length;
    int[][] dp = new int[n][capacity + 1];
    // Initialize the column for capacity=0, where profit is 0 regardless of items considered
    for(int i=0; i < n; i++)
      dp[i][0] = 0;
    // If we only have one item, accept it if its weight does not exceed the capacity
    for(int c=0; c <= capacity; c++) {
      if(weights[0] <= c)
        dp[0][c] = profits[0];
    }
    // Process all subarrays for every capacity level
    for(int i=1; i < n; i++) {
      for(int c=1; c <= capacity; c++) {
        int profit1= 0, profit2 = 0;
        // If the current item's weight is within capacity, include it in the calculation
        if(weights[i] <= c)
          profit1 = profits[i] + dp[i-1][c-weights[i]];
        // Case where the current item is not included
        profit2 = dp[i-1][c];
        // Select the maximum of including or excluding the current item
        dp[i][c] = Math.max(profit1, profit2);
      }
    }
    // The bottom-right cell contains the maximum profit
    return dp[n-1][capacity];
  }
  public static void main(String[] args) {
    Knapsack ks = new Knapsack();
    int[] profits = {1, 6, 10, 16};
    int[] weights = {1, 2, 3, 5};
    int maxProfit = ks.solveKnapsack(profits, weights, 7);
    System.out.println("Total knapsack profit ---> " + maxProfit);
    maxProfit = ks.solveKnapsack(profits, weights, 6);
    System.out.println("Total knapsack profit ---> " + maxProfit);
  }
}

@tab JavaScript

class Knapsack {
  solveKnapsack(profits, weights, capacity) {
    // Base case validation
    if (capacity <= 0 || profits.length === 0 || weights.length !== profits.length)
      return 0;
    const n = profits.length;
    const dp = new Array(n).fill(0).map(() => new Array(capacity + 1).fill(0));
    // Initialize the column for capacity=0, where profit is 0 regardless of items considered
    for (let i = 0; i < n; i++)
      dp[i][0] = 0;
    // If we only have one item, accept it if its weight does not exceed the capacity
    for (let c = 0; c <= capacity; c++) {
      if (weights[0] <= c)
        dp[0][c] = profits[0];
    }
    // Process all subarrays for every capacity level
    for (let i = 1; i < n; i++) {
      for (let c = 1; c <= capacity; c++) {
        let profit1 = 0, profit2 = 0;
        // If the current item's weight is within capacity, include it in the calculation
        if (weights[i] <= c)
          profit1 = profits[i] + dp[i - 1][c - weights[i]];
        // Case where the current item is not included
        profit2 = dp[i - 1][c];
        // Select the maximum of including or excluding the current item
        dp[i][c] = Math.max(profit1, profit2);
      }
    }
    // The bottom-right cell contains the maximum profit
    return dp[n - 1][capacity];
  }
}
const ks = new Knapsack();
const profits = [1, 6, 10, 16];
const weights = [1, 2, 3, 5];
let maxProfit = ks.solveKnapsack(profits, weights, 7);
console.log("Total knapsack profit ---> " + maxProfit);
maxProfit = ks.solveKnapsack(profits, weights, 6);
console.log("Total knapsack profit ---> " + maxProfit);

@tab Python

class Knapsack:
    def solveKnapsack(self, profits, weights, capacity):
        # Base case validation
        if capacity <= 0 or len(profits) == 0 or len(weights) != len(profits):
            return 0
        n = len(profits)
        dp = [[0] * (capacity + 1) for _ in range(n)]
        # Initialize the column for capacity=0, where profit is 0 regardless of items considered
        for i in range(n):
            dp[i][0] = 0
        # If we only have one item, accept it if its weight does not exceed the capacity
        for c in range(capacity + 1):
            if weights[0] <= c:
                dp[0][c] = profits[0]
        # Process all subarrays for every capacity level
        for i in range(1, n):
            for c in range(1, capacity + 1):
                profit1, profit2 = 0, 0
                # If the current item's weight is within capacity, include it in the calculation
                if weights[i] <= c:
                    profit1 = profits[i] + dp[i - 1][c - weights[i]]
                # Case where the current item is not included
                profit2 = dp[i - 1][c]
                # Select the maximum of including or excluding the current item
                dp[i][c] = max(profit1, profit2)
        # The bottom-right cell contains the maximum profit
        return dp[n - 1][capacity]
ks = Knapsack()
profits = [1, 6, 10, 16]
weights = [1, 2, 3, 5]
max_profit = ks.solveKnapsack(profits, weights, 7)
print("Total knapsack profit --->", max_profit)
max_profit = ks.solveKnapsack(profits, weights, 6)
print("Total knapsack profit --->", max_profit)

@tab Go

package main
import (
    "fmt"
)
type Knapsack struct{}
func (ks Knapsack) SolveKnapsack(profits []int, weights []int, capacity int) int {
    // Base case validation
    if capacity <= 0 || len(profits) == 0 || len(weights) != len(profits) {
        return 0
    }
    n := len(profits)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }
    // Initialize the column for capacity=0, where profit is 0 regardless of items considered
    for i := 0; i < n; i++ {
        dp[i][0] = 0
    }
    // If we only have one item, accept it if its weight does not exceed the capacity
    for c := 0; c <= capacity; c++ {
        if weights[0] <= c {
            dp[0][c] = profits[0]
        }
    }
    // Process all subarrays for every capacity level
    for i := 1; i < n; i++ {
        for c := 1; c <= capacity; c++ {
            profit1, profit2 := 0, 0
            // If the current item's weight is within capacity, include it in the calculation
            if weights[i] <= c {
                profit1 = profits[i] + dp[i-1][c-weights[i]]
            }
            // Case where the current item is not included
            profit2 = dp[i-1][c]
            // Select the maximum of including or excluding the current item
            dp[i][c] = max(profit1, profit2)
        }
    }
    // The bottom-right cell contains the maximum profit
    return dp[n-1][capacity]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func main() {
    ks := Knapsack{}
    profits := []int{1, 6, 10, 16}
    weights := []int{1, 2, 3, 5}
    maxProfit := ks.SolveKnapsack(profits, weights, 7)
    fmt.Println("Total knapsack profit --->", maxProfit)
    maxProfit = ks.SolveKnapsack(profits, weights, 6)
    fmt.Println("Total knapsack profit --->", maxProfit)
}

:::