0-1 Knapsack Problem | Dynamic Programming

For this article we discuss a classic dynamic programming problem which is 0-1 knapsack. The problem we are interested in is given a series of objects with a weight and value and a knapsack that can carry a set amount of weight, what is the maximum object value we can put in our knapsack without exceeeding the weight.

Input

weights: an array of integers that denote the weights of objects
values: an array of integers that denote the values of objects
max_weight: the maximum weight in the knapsack

Output

the maximum value in the knapsack

Examples

Example 1:

Input:

1weights = [3, 4, 7]
2values = [4, 5, 8]
3max_weight = 7

Output: 5

Explanation:

We have a knapsack of max limit 7 with 3 objects of weight-value pairs of [3,4],[4,5],[7,8] then the maximal value we can achieve is using the first 2 objects to obtain value 4 + 5 = 9.

The other possibilities would all be only 1 object in our knapsack which would only yield values 4, 5, and 9.

Try it yourself

Solution

Brute force

A brute force method would enumerate all the possibilities such that for every object we try including it into our knapsack which would result in time complexity O(2^n) where n is the total number of objects. This is due to the fact that one would have to use some sort of recursive function and try every object combination and checking which one contains the maximum value.

2D Dynamic Programming

For this problem, we introduce a classic dynamic programming solution which has time complexity O(n * w) where w is the target weight. The intuition for this DP is to maintain a 2-D array where 1 dimension maintains the current object we are considering and another dimension considers the weight that we use up.

In other words, dp[i][j] denotes the maximal value obtainable using the first i objects and only taking up j weight. We then have dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]). Evidently in most cases a time complexity of O(n * w) would be better then O(2^n) except for cases where n is sufficiently small and/or w is sufficiently large.

2D to 1D Optimization

We have discussed how to do knapsack using 2-D DP but now we discuss how we can optimize this into 1-D DP. We realize that for the first dimension keeping track of the objects that we only ever use the previous row so therefore, we can simply remove that dimension from out DP without consequence.

The basic idea is to maintain a 1-D array that keeps track of the maximal value we can get for a certain amount of weight. We can loop from the largest value to the smallest value to ensure we do not use a given object twice. Looping backwards ensures we only ever use DP values from the previous row which is equivalent to the 2-D DP except we can save some memory.

The dp state can then be calculated using dp[j] = max(dp[j], dp[j - weight[i]] + value[i]). We first set each array element to be -1 which means we have not reached that weight. If we have not reached that weight we should skip it and make sure to not compute the value for that index.

Here is a graphic to demonstrate this idea. Note that when a weight is smaller than the array index we stop considering the index as it means our weight is greater than the current capacity of the knapsack.

1from typing import List
2
3def knapsack(weights: List[int], values: List[int], max_weight: int) -> int:
4    # initialize the array and set values to -1 except for index 0
5    dp = [-1] * (max_weight + 1)
6    dp[0] = 0
7    # loop through the objects
8    for i in range(len(weights)):
9        # loop through the dp indexes from largest value to smallest one
10        for j in range(max_weight, weights[i] - 1, -1):
11            # check if we have reached the weight value before
12            if dp[j - weights[i]] != -1:
13                dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
14    return max(dp)
15
16if __name__ == '__main__':
17    weights = [int(x) for x in input().split()]
18    values = [int(x) for x in input().split()]
19    max_weight = int(input())
20    res = knapsack(weights, values, max_weight)
21    print(res)
22

1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7    public static int knapsack(List<Integer> weights, List<Integer> values, int maxWeight) {
8        // make a dp array and fill the array with -1 making sure to set weight 0 to value 0
9        int [] dp = new int[maxWeight + 1];
10        Arrays.fill(dp, -1);
11        dp[0] = 0;
12        // loop through every object which is simply length of weights array, values array also works as they should be same length
13        for (int i = 0; i < weights.size(); i++) {
14            // as discussed make sure to loop from highest value backwards to avoid reusing the same object
15            for (int j = maxWeight; j >= weights.get(i); j--) {
16                // if we establish a particular weight is achievable we update out current weight maximum value
17                if(dp[j - weights.get(i)] != -1) {
18                    dp[j] = Math.max(dp[j], dp[j - weights.get(i)] + values.get(i));
19                }
20            }
21        }
22        int maxValue = -1;
23        for (int i = 0; i < maxWeight + 1; i++) {
24            maxValue = Math.max(maxValue, dp[i]);
25        }
26        return maxValue;
27    }
28
29    public static List<String> splitWords(String s) {
30        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
31    }
32
33    public static void main(String[] args) {
34        Scanner scanner = new Scanner(System.in);
35        List<Integer> weights = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
36        List<Integer> values = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
37        int maxWeight = Integer.parseInt(scanner.nextLine());
38        scanner.close();
39        int res = knapsack(weights, values, maxWeight);
40        System.out.println(res);
41    }
42}
43

0-1 Knapsack variants

Hopefully, this should give you a good idea of how the algorithm works. A trick that may be useful to know is that there are more than one method to use dynamic programming for this problem. We discussed here achieving the maximum value for a given weight but we similarly could have done the minimum weight achievable for a particular value instead to achieve similar results.

0-1 Knapsack and Coin Change, what's the connection?

Some of you may have realized the similarities bore to the coin change problem(Coin Change). In fact the coin change can be thought of as a variant of the 0-1 Knapsack Problem. If we have dp[i] instead of representing the maximum value achievable for a certain weight we change it to represent the minimum weight required to achieve a certain value and change all the weights to 1 we now have the solution to the coin change problem. Our new dp transition is then simply dp[i] = min(dp[i], dp[i - values[j]] + 1). The implementation specifics is left as an exercise to the reader and should be reasonably similar to the 0-1 Knapsack Problem implementation. Remember that you can use a coin multiple times which is another difference betweeen coin change and the 0-1 knapsack problem. Now onto the implementation,

1public static int knapsack(int weights[], int values[], int target) {
2    // make a dp array and fill the array with -1 making sure to set weight 0 to value 0
3    int [] dp = new int[target + 1];
4    Arrays.fill(dp, -1);
5    dp[0] = 0;
6    // loop through every object which is simply length of weights array, values array also works as they should be same length
7    for (int i = 0; i < weights.length; i++) {
8        // as discussed make sure to loop from highest value backwards to avoid reusing the same object
9        for (int j = target; j >= weights[i]; j--) {
10            // if we establish a particular weight is achievable we update out current weight maximum value
11            if(dp[j - weights[i]] != -1) {
12                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
13            }
14        }
15    }
16    return dp[target];
17}
18

1def knapsack(weights, values, target):
2    # initialize the array and set values to -1 except for index 0
3    dp = [-1] * (target + 1)
4    dp[0] = 0
5    # loop through the objects
6    for i in range(len(weights)):
7        # loop through the dp indexes from largest value to smallest one
8        for j in range(target, weights[i] - 1, -1):
9            # check if we have reached the weight value before
10            if dp[j - weights[i]] != -1:
11                dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
12    return dp[target]
13

Overview

Basic Data Structures

Basic Algorithms

Warm Up

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Introduction

DFS on Tree

Binary Search Tree

Combinatorial Search

Memoization

Pruning

Dedup

Additional Practices

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Sequence

Grid

Dynamic number of subproblems

Partition

Interval

Two Sequences

Game Theory

0-1 Knapsack

Bitmask

Tree

Introduction

Generalized

Binary Search

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Greedy

Monotonic Stack

Line Sweep

Interval

Tree Traversal without Recursion

Composite Patterns

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

0-1 Knapsack Problem | Dynamic Programming

Input

Output

Examples

Example 1:

Try it yourself

Solution

Brute force

2D Dynamic Programming

2D to 1D Optimization

0-1 Knapsack variants