0/1 Knapsack Problem Pseudo Code

4 min read Jul 17, 2024

0/1 Knapsack Problem Pseudocode

Introduction

The 0/1 Knapsack Problem is a classic problem in computer science and operations research that involves finding the optimal way to pack a set of items of different weights and values into a knapsack of limited capacity. The goal is to maximize the total value of the items in the knapsack without exceeding its weight capacity.

Problem Statement

Given a set of n items, each with a weight w_i and a value v_i, and a knapsack with a capacity W, determine the subset of items to include in the knapsack to maximize the total value while not exceeding the knapsack's weight capacity.

Pseudocode

Here is a pseudocode solution for the 0/1 Knapsack Problem using dynamic programming:

**Knapsack(W, n, w, v)**
  // Create a 2D array to store the maximum value for each subproblem
  **dp** = new array[n+1][W+1]

  // Initialize the base case
  **dp[0][0]** = 0

  // Fill up the table in a bottom-up manner
  for **i** from 1 to **n**
    for **j** from 1 to **W**
      if **w[i-1]** <= **j**
        **dp[i][j]** = max(**dp[i-1][j]**, **dp[i-1][j-w[i-1]]** + **v[i-1]**)
      else
        **dp[i][j]** = **dp[i-1][j]**

  // Return the maximum value
  return **dp[n][W]**

Explanation

The pseudocode uses a 2D array dp to store the maximum value for each subproblem. The array has dimensions (n+1) x (W+1).
The base case is initialized as dp[0][0] = 0, indicating that the maximum value for no items and zero capacity is zero.
The table is filled up in a bottom-up manner, iterating over each item and each possible weight from 1 to W.
For each subproblem, if the current item's weight is less than or equal to the current weight j, the maximum value is the maximum of two options: (a) excluding the current item (dp[i-1][j]) and (b) including the current item (dp[i-1][j-w[i-1]] + v[i-1]).
If the current item's weight exceeds the current weight j, the maximum value is the same as the maximum value without including the current item (dp[i-1][j]).
Finally, the maximum value for the original problem is returned as dp[n][W].

Time Complexity

The time complexity of the pseudocode is O(nW), where n is the number of items and W is the knapsack capacity.

Space Complexity

The space complexity of the pseudocode is O(nW), which is the size of the 2D array dp.

0/1 Knapsack Problem Pseudo Code