0-1 Knapsack Problem - Java Solution

1. Introduction

In this blog post, we will dive into the classic 0-1 Knapsack problem, a fundamental problem in combinatorial optimization. The problem is to maximize the total value of items that can be put into a knapsack with a given capacity, considering that each item can be taken or left (0-1 property).

Problem

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. You cannot break an item, either pick the complete item or don’t pick it (0-1 property).

Example:

Input: val[] = {60, 100, 120}, wt[] = {10, 20, 30}, W = 50

Output: 220

Explanation: Choose the 2nd and 3rd items having weights 20 and 30. The total value we can obtain is 220.

2. Solution Steps

1. Use dynamic programming to build a 2D array dp where dp[i][w] represents the maximum value that can be obtained with the first i items and a weight limit of w.

2. For each item, decide whether to include it in the knapsack or not.

3. Update the dp table according to the decision made.

4. The answer will be in dp[n][W], where n is the number of items and W is the knapsack capacity.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] val = {60, 100, 120};
        int[] wt = {10, 20, 30};
        int W = 50;
        System.out.println("Maximum value obtained: " + knapSack(W, wt, val, val.length));
    }

    // Method to solve the 0-1 Knapsack problem
    public static int knapSack(int W, int[] wt, int[] val, 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 (wt[i - 1] <= w) {
                    dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        return dp[n][W];
    }
}

Output:

Maximum value obtained: 220

Explanation:

For the given input, the knapSack method calculates the maximum value that can be obtained with the items {60, 100, 120} and weights {10, 20, 30}, within a weight limit of 50. The dynamic programming approach ensures that the maximum value obtained is 220, by choosing the 2nd and 3rd items, which give the maximum value without exceeding the weight limit.