Solving the Knapsack Problem Using Dynamic Programming in Java

Now we’ll explore the Knapsack problem using a different approach: the Dynamic Programming (DP) method. Unlike the greedy approach, which sometimes provides suboptimal results, the DP approach guarantees an optimal solution to the problem. This problem is also known as the 0/1 Knapsack Problem.

Knapsack Problem Overview:

The goal of the knapsack problem is to maximize the total profit we can carry in a knapsack of limited capacity. Each item has a weight and a profit. We need to select items to fill the knapsack such that the total weight does not exceed the capacity, and the total profit is maximized.

Problem Constraints:

• We have n items, each with a given weight and profit.
• The total weight of selected items must not exceed the knapsack capacity W.
• We either take the whole item or leave it—there are no partial selections.

Dynamic Programming Approach:

We use a 2D table to solve the problem. The DP table stores the maximum profit for each combination of items and capacities. This allows us to explore all possibilities and derive the optimal solution.

Steps to Solve:

1. Create a DP table with dimensions [n+1][W+1] where n is the number of items and W is the knapsack capacity.
2. Fill the DP table based on whether to include or exclude an item:
   • If the current item’s weight is less than or equal to the current capacity, take the maximum of including or excluding the item.
   • If the current item’s weight exceeds the current capacity, exclude the item.
3. Trace the maximum profit by checking the last cell of the DP table.

Java Code for the Dynamic Programming Approach:

import java.util.Scanner;

public class KnapsackDP {
    public static int knapsack(int W, int[] weights, int[] profits, int n) {
        int[][] dp = new int[n + 1][W + 1];
        
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0; 
                } else if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(profits[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w]; 
                }
            }
        }
        return dp[n][W]; 
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        System.out.println("Enter the number of items:");
        int n = sc.nextInt();
        
        int[] weights = new int[n];
        int[] profits = new int[n];
        
        System.out.println("Enter the weights and profits of the items:");
        for (int i = 0; i < n; i++) {
            System.out.print("Item " + (i + 1) + " weight: ");
            weights[i] = sc.nextInt();
            System.out.print("Item " + (i + 1) + " profit: ");
            profits[i] = sc.nextInt();
        }
        
        System.out.println("Enter the capacity of the knapsack:");
        int W = sc.nextInt();
        
        int maxProfit = knapsack(W, weights, profits, n);
        sc.close();
        System.out.println("Maximum profit: " + maxProfit);
    }
}

Explanation:

1. Input Handling: We start by asking for the number of items, their weights, profits, and the knapsack’s capacity.
2. DP Table Initialization: We initialize a 2D table dp[][] where each cell dp[i][w] represents the maximum profit for the first i items and capacity w.
3. Building the Table: For each item, we either include it (if the weight allows) or exclude it based on which option gives more profit.
4. Final Profit: The last cell of the DP table contains the maximum profit that can be achieved.

Example Output:

Enter the number of items:
4
Enter the weights and profits of the items:
Item 1 weight: 2
Item 1 profit: 10
Item 2 weight: 3
Item 2 profit: 5
Item 3 weight: 4
Item 3 profit: 15
Item 4 weight: 5
Item 4 profit: 7
Enter the capacity of the knapsack:
7
Maximum profit: 25

Complexity:

The time complexity of this approach is O(n * W), where n is the number of items and W is the knapsack capacity. This is more computationally intensive than the greedy approach, but guarantees optimality.