Problem 3: Knapsack Problem

The knapsack problem is a classic optimization problem in computer science and is often used as an example to demonstrate the use of dynamic programming.

In this problem, we are given a set of items, each with its own weight and value, and a knapsack with a maximum weight capacity. The goal is to determine the maximum total value of items that can be placed in the knapsack without exceeding its capacity.

For example, consider the following set of items:

1Item 1: weight = 2, value = 3
2Item 2: weight = 3, value = 4
3Item 3: weight = 4, value = 5
4Item 4: weight = 5, value = 6

Suppose we have a knapsack with a capacity of 7. To solve this problem using dynamic programming, we can use a 2D matrix to store the maximum total values for different combinations of items and knapsack capacities. We can then fill in the matrix iteratively using the following rules:

• If the current item can fit in the knapsack (i.e., its weight is less than or equal to the knapsack capacity), we have two choices:
  • Include the item in the knapsack: in this case, the total value is the sum of the value of the current item and the maximum value obtained by considering the remaining items and the remaining capacity in the knapsack.
  • Exclude the item from the knapsack: in this case, the total value is the same as the maximum value obtained by considering the remaining items and the full capacity of the knapsack. We take the maximum of these two choices and store it in the matrix at the corresponding position.
• If the current item cannot fit in the knapsack, the total value is the same as the maximum value obtained by considering the remaining items and the full capacity of the knapsack.

Here's an example implementation in Java:

xxxxxxxxxx

class Main {

    public static int knapsack(int[] weights, int[] values, int capacity) {

        int n = weights.length;

        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];

    }

​

    public static void main(String[] args) {

        int[] weights = {2, 3, 4, 5};

        int[] values = {3, 4, 5, 6};

        int capacity = 7;

        int maxProfit = knapsack(weights, values, capacity);

        System.out.println("The maximum profit that can be obtained is: " + maxProfit);

    }

}