Knapsack Problem

The Knapsack Problem is a classic optimization problem in computer science and mathematics. Given a set of items, each with a weight and a value, and a maximum weight capacity for a knapsack, the goal is to determine the most valuable combination of items to include in the knapsack without exceeding its capacity.

In other words, we want to maximize the total value of the items in the knapsack while keeping the total weight below the maximum capacity.

The 0/1 in the name of the problem refers to the restriction that each item can only be included once (0) or excluded (1) from the knapsack. We either take the item or we don't, we cannot take a fraction of it.

To solve the 0/1 knapsack problem, we can use dynamic programming.

Let's define a 2D array dp of size (n + 1) x (capacity + 1), where

• n is the number of items
• capacity is the maximum weight capacity of the knapsack

The value of dp[i][j] represents the maximum value that can be obtained using the first i items and a knapsack of capacity j.

We can use the following recursive formula to fill the dp array:

1if (weights[i - 1] <= j) {
2  dp[i][j] = max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j]);
3} else {
4  dp[i][j] = dp[i - 1][j];
5}

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

    // replace with your Java logic here

    int[] values = {60, 100, 120};

    int[] weights = {10, 20, 30};

    int capacity = 50;

    int maxProfit = knapSack(capacity, weights, values, weights.length);

    System.out.println("The maximum profit is: " + maxProfit);

  }

​

  static int knapSack(int capacity, int[] weights, int[] values, int n) {

    int[][] dp = new int[n + 1][capacity + 1];

​

    for (int i = 0; i <= n; i++) {

      for (int j = 0; j <= capacity; j++) {

        if (i == 0 || j == 0) {

          dp[i][j] = 0;

        } else if (weights[i - 1] <= j) {

          dp[i][j] = Math.max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j]);

        } else {

          dp[i][j] = dp[i - 1][j];

        }

      }

    }

​

    return dp[n][capacity];

  }

}