1. Introduction

The 0-1 Knapsack problem is a classic optimization problem in the field of algorithms and dynamic programming. Given a set of items, each with a weight and a value, the goal is to determine the number of each item to include in a knapsack so that the total weight is less than or equal to a given limit and the total value is as large as possible.

It’s called 0-1 knapsack because you can’t break an item; you either take it (1) or leave it (0).

2. Program Steps

1. Define a function knapsack that takes weights, values, the number of items, and the capacity of the knapsack as parameters.

2. Initialize a 2D table where the cell at the i-th row and j-th column represents the maximum value achievable with the first i items and total knapsack weight capacity j.

3. Fill up the table using a bottom-up approach based on the recurrence relation.

4. Return the value in the last cell of the table, which represents the solution to the problem.

5. In the main method, define weights, values, and knapsack capacity. Call the knapsack function to get the maximum value.

3. Code Program

class KnapsackProblem {

    public static int knapsack(int[] weights, int[] values, int n, int W) {
        int[][] K = 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) {
                    K[i][w] = 0;
                } else if (weights[i - 1] <= w) {
                    K[i][w] = Math.max(values[i - 1] + K[i - 1][w - weights[i - 1]], K[i - 1][w]);
                } else {
                    K[i][w] = K[i - 1][w];
                }
            }
        }

        return K[n][W];
    }

    public static void main(String[] args) {
        int[] values = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int W = 50;
        int n = values.length;

        System.out.println("Maximum value that can be obtained: " + knapsack(weights, values, n, W));
    }
}

Output:

Maximum value that can be obtained: 220

4. Step By Step Explanation

1. The knapsack function initializes a 2D array K to store intermediate results. The idea is to compute the maximum value for every possible weight from 0 to W using items from 1 through n.

2. If the current item's weight (weights[i-1]) is less than or equal to the current weight w, then the value in the cell is the maximum of either:

– The value of the current item plus the maximum value achievable with the remaining weight (w – weights[i-1]) and using items 1 through i-1.

– The maximum value achievable without the current item (using items 1 through i-1 and weight w).

3. If the current item's weight exceeds the current weight w, then the cell's value is simply the maximum value achievable without the current item.

4. The main function provides an example set of items and a knapsack capacity. The result, 220, indicates that the best combination of items to maximize the value without exceeding the weight limit involves taking the items with values 100 and 120.