In this artcile, we will learn to resolve the 0-1 Knapsack problem in Java by using a dynamic programming algorithm

## Problem

Given a knapsack with weight capacity, and a set of items, each item with a weight and a value

Determine the maximum value of items to include in the given knapsack so that the total weight is less than or equal to the knapsack capacity

## Example

Given 3 items with weights = {10, 20 , 30} and values = {60, 100, 120} respectively, knapsack weight capacity is 50

The maximum value of items to include in the knapsack is 220

## Analysis

We have 2 options at each collecting step

Including the

`i`

item if not exceeding the weight limitExcluding the

`i`

item if exceeding the weight limit

## Dynamic Programming Approach

Fill up a cache matrix `int[][] cache = new int[N+1][W+1]`

with

0 to

`N`

items as columns0 to

`W`

weight-limit as rowseach matrix cell

`cache[i][w]`

is the maximum value can be attained with weight less than or equal to`w`

using`i`

items

```
public class DP_Knapsack {
int findMaxValueOfKnapSack(int[] values, int[] weights, int W, int N) {
int[][] cache = 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) {
cache[i][w] = 0;
}
else if (weights[i-1] > w) {
cache[i][w] = cache[i-1][w];
} else {
cache[i][w] = Math.max(cache[i-1][w], cache[i-1][w-weights[i-1]] + values[i-1]);
}
}
}
return cache[N][W];
}
public static void main(String[] args) {
DP_Knapsack knapsack = new DP_Knapsack();
int[] values = {60, 100, 120};
int[] weights = {10, 20, 30};
int weightLimit = 50;
int noOfItems = values.length;
System.out.println(knapsack.findMaxValueOfKnapSack(values, weights, weightLimit, noOfItems));
}
}
```

`i`

is the current item`w`

is the current weight limit`weights[i-1]`

is weight of current item as`int[] weights`

is 0 based index`values[i-1]`

is value of current item as`int[] values`

is 0 based index`cache[i][w]`

is maximum value of current item as`int[][] cache`

is 1 based index`weights[i-1] > w`

weight of the current item is more than the weight limit`cache[i][w] = cache[i-1][w]`

excludes the current item`cache[i-1][w-weights[i-1]] + values[i-1]`

includes the current item