# 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.