# HelloKoding

Practical coding guides

# 0-1 Knapsack Problem

In this article, you will learn to analyze and resolve the 0-1 Knapsack problem by using an dynamic programming algorithm

## Problem

• Given a set of items, each with a weight and a value
• Determine the maximum value of items to include in a collection so that the total weight is less than or equal to a given limit

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

## Dynamic programming approach

Have 2 options at each collecting step

• Including the `i` item if not exceeding the weight limit
• Excluding the `i` item if exceeding the weight limit

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

• 0 to `N` items as columns
• 0 to `W` weight-limit as rows
• each matrix cell `cache[i][w]` is the maximum value can be attained with weight less than or equal to `w` using `i` items

DP_Knapsack.java

``````package com.hellokoding.algorithm;

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