## Introduction

Consider a set of items with a weight * w* and profit

*associated with each one of them. If we have a knapsack of capacity*

**p***, we want to fill it with the maximum set of items that give us maximum profit. A fundamental constraint for this problem is that we can include an item or not, we cannot include fractions of it. This problem and its solution problem is the*

**W****0/1 Knapsack Problem**. The 0/1 part highlights the fact that we can only include integral items.

## Problem Example for 0/1 Knapsack Problem

We can consider the set of items as a bi-dimensional array, and in Java, we can write it for instance as an array literal like *{ {w1, p1}, {w2, p2}, …}*. Consider the following input for the problem:

**N**= 3 items with the following values in terms of profit and weight:*{**{*1, 5},,*{*2, 15}}*{*3, 6}

**W**= 10 capacity

We cannot include the *{2, 15}* item, because it exceeds the maximum weight. We cannot include both

*and*

*{*1, 5}*, because the sum of their weights is greater than W. We can conclude that we can obtain the maximum profit by including*

*{*3, 6}*alone.*

*{*3, 6}## Simple Solution for 0/1 Knapsack Problem

The most immediate solution that comes to mind is to consider all the possible sub-sets and choose the sub-set with the maximum profit. Performing such tasks recursively, in evaluating each single item we have to compare these two cases, to see which gives the maximum profit:

- The current subset plus the current item if its weight is lower or equal to W (otherwise we continue with the next step of the recursion)
- The current subset without the current item

The steps described above are shown in the following code snippet:

```
class KnapSack01UnitTest {
@Test
public void knapSack01Test() throws Exception {
int items[][] = { { 1, 5 }, { 2, 15 }, { 3, 6 } };
int W = 10;
int N = items.length;
System.out.println(knapSackEvaluation(W, items, N));
}
private int knapSackEvaluation(int W, int items[][], int N) {
if (N == 0 || W == 0) {
return 0;
}
if (items[N - 1][1] > W) {
return knapSackEvaluation(W, items, N - 1);
} else {
return maxInteger(items[N - 1][0] + knapSackEvaluation(W - items[N - 1][1], items, N - 1), knapSackEvaluation(W, items, N - 1));
}
}
private int maxInteger(int a, int b) {
return (a > b) ? a : b;
}
}
```

### Performance Considerations for the Above 0/1 Knapsack Problem Algorithm

The time complexity of the above algorithm is O(2^{N}).

## Conclusion

In this article, we have seen a trivial way to solve the **0/1 Knapsack Problem**. The example code is available on GitHub.