0-1 Knapsack

We want to discuss a classic dynamic programming problem, which is 0-1 knapsack. Given a series of objects with a weight and a 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 exceeding the weight constraint?

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 capacity of the knapsack

Output

the maximum value in the knapsack

Examples

Example 1:

Input:

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

Output: 9

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 | DFS | Combinatorial Search

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 can be done with a recursive combinatorial search where, for every item, we either choose to include it or not, then checking which possibility results in the greatest value while not exceeding the maximum weight.

Here is an illustration of the idea, where the left represents picking up the item and the right giving up the item:

Note that the largest value while not exceeding the maximum weight is 9.

1from typing import List
2
3# helper function that returns the maximum value when considering
4# the first n items and remaining available weight remaining_weight
5def knapsack_helper(weights: List[int], values: List[int], remaining_weight: int, n: int) -> int:
6    # base case: if there are no items or no available weight in the knapsack to use, the maximum value is 0
7    if n == 0 or remaining_weight == 0:
8        return 0
9    # if the weight of the current item exceeds the available weight,
10    # skip the current item and process the next one
11    if weights[n - 1] > remaining_weight:
12        return knapsack_helper(weights, values, remaining_weight, n - 1)
13    # recurrence relation: choose the maximum of two possibilities:
14    #   (1) pick up the current item: current value + maximum value with the rest of the items
15    #   (2) give up the current item: maximum value with the rest of the items
16    return max(
17        values[n - 1] + knapsack_helper(weights, values, remaining_weight - weights[n - 1], n - 1),
18        knapsack_helper(weights, values, remaining_weight, n - 1),
19    )
20
21def knapsack(weights: List[int], values: List[int], max_weight: int) -> int:
22    n = len(weights)
23    return knapsack_helper(weights, values, max_weight, n)
24
25if __name__ == "__main__":
26    weights = [int(x) for x in input().split()]
27    values = [int(x) for x in input().split()]
28    max_weight = int(input())
29    res = knapsack(weights, values, max_weight)
30    print(res)
31
1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7    // helper function that returns the maximum value when considering
8    // the first n items and remaining available weight remainingWeight
9    public static int knapsackHelper(List<Integer> weights, List<Integer> values, int remainingWeight, int n) {
10        // base case: if there are no items or no available weight in the knapsack to use, the maximum value is 0
11        if (n == 0 || remainingWeight == 0) {
12            return 0;
13        }
14        // if the weight of the current item exceeds the available weight,
15        // skip the current item and process the next one
16        if (weights.get(n - 1) > remainingWeight) {
17            return knapsackHelper(weights, values, remainingWeight, n - 1);
18        }
19        // recurrence relation: choose the maximum of two possibilities:
20        //   (1) pick up the current item: current value + maximum value with the rest of the items
21        //   (2) give up the current item: maximum value with the rest of the items
22        return Math.max(
23            values.get(n - 1) + knapsackHelper(weights, values, remainingWeight - weights.get(n - 1), n - 1),
24            knapsackHelper(weights, values, remainingWeight, n - 1));
25    }
26
27    public static int knapsack(List<Integer> weights, List<Integer> values, int maxWeight) {
28        int n = weights.size();
29        return knapsackHelper(weights, values, maxWeight, n);
30    }
31
32    public static List<String> splitWords(String s) {
33        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
34    }
35
36    public static void main(String[] args) {
37        Scanner scanner = new Scanner(System.in);
38        List<Integer> weights = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
39        List<Integer> values = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
40        int maxWeight = Integer.parseInt(scanner.nextLine());
41        scanner.close();
42        int res = knapsack(weights, values, maxWeight);
43        System.out.println(res);
44    }
45}
46
1"use strict";
2
3// helper function that returns the maximum value when considering
4// the first n items and remaining available weight remainingWeight
5function knapsackHelper(weights, values, remainingWeight, n) {
6    // base case: if there are no items or no available weight in the knapsack to use, the maximum value is 0
7    if (n === 0 || remainingWeight === 0) {
8        return 0;
9    }
10    // if the weight of the current item exceeds the available weight,
11    // skip the current item and process the next one
12    if (weights[n - 1] > remainingWeight) {
13        return knapsackHelper(weights, values, remainingWeight, n - 1);
14    }
15    // recurrence relation: choose the maximum of two possibilities:
16    //   (1) pick up the current item: current value + maximum value with the rest of the items
17    //   (2) give up the current item: maximum value with the rest of the items
18    return Math.max(
19        values[n - 1] + knapsackHelper(weights, values, remainingWeight - weights[n - 1], n - 1),
20        knapsackHelper(weights, values, remainingWeight, n - 1),
21    );
22}
23function knapsack(weights, values, maxWeight) {
24    const n = weights.length;
25    return knapsackHelper(weights, values, maxWeight, n);
26}
27
28function splitWords(s) {
29    return s === "" ? [] : s.split(" ");
30}
31
32function* main() {
33    const weights = splitWords(yield).map((v) => parseInt(v));
34    const values = splitWords(yield).map((v) => parseInt(v));
35    const maxWeight = parseInt(yield);
36    const res = knapsack(weights, values, maxWeight);
37    console.log(res);
38}
39
40class EOFError extends Error {}
41{
42    const gen = main();
43    const next = (line) => gen.next(line).done && process.exit();
44    let buf = "";
45    next();
46    process.stdin.setEncoding("utf8");
47    process.stdin.on("data", (data) => {
48        const lines = (buf + data).split("\n");
49        buf = lines.pop();
50        lines.forEach(next);
51    });
52    process.stdin.on("end", () => {
53        buf && next(buf);
54        gen.throw(new EOFError());
55    });
56}
57
1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <limits>
5#include <sstream>
6#include <string>
7#include <vector>
8
9// helper function that returns the maximum value when considering
10// the first n items and remaining available weight remaining_weight
11int knapsackHelper(std::vector<int>& weights, std::vector<int>& values, int remaining_weight, int n) {
12    // base case: if there are no items or no available weight in the knapsack to use, the maximum value is 0
13    if (n == 0 || remaining_weight == 0) {
14        return 0;
15    }
16    // if the weight of the current item exceeds the available weight,
17    // skip the current item and process the next one
18    if (weights[n - 1] > remaining_weight) {
19        return knapsackHelper(weights, values, remaining_weight, n - 1);
20    }
21    // recurrence relation: choose the maximum of two possibilities:
22    //   (1) pick up the current item: current value + maximum value with the rest of the items
23    //   (2) give up the current item: maximum value with the rest of the items
24    return std::max(
25        values[n - 1] + knapsackHelper(weights, values, remaining_weight - weights[n - 1], n - 1),
26        knapsackHelper(weights, values, remaining_weight, n - 1));
27}
28int knapsack(std::vector<int>& weights, std::vector<int>& values, int max_weight) {
29    int n = weights.size();
30    return knapsackHelper(weights, values, max_weight, n);
31}
32
33template<typename T>
34std::vector<T> get_words() {
35    std::string line;
36    std::getline(std::cin, line);
37    std::istringstream ss{line};
38    ss >> std::boolalpha;
39    std::vector<T> v;
40    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
41    return v;
42}
43
44void ignore_line() {
45    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
46}
47
48int main() {
49    std::vector<int> weights = get_words<int>();
50    std::vector<int> values = get_words<int>();
51    int max_weight;
52    std::cin >> max_weight;
53    ignore_line();
54    int res = knapsack(weights, values, max_weight);
55    std::cout << res << '\n';
56}
57

DFS + Memoization

We can optimize the brute force solution by storing answers that have already been computed in a 2D array called dp. In this case dp[n][remaining_weight] stores the maximum value when considering the first n items with a maximum available weight of remaining_weight. If the answer already exists for dp[n][remaining_weight], then we immediately use that result. Otherwise, we recurse and store the result of the recurrence.

1from typing import List
2
3def knapsack_helper(
4    weights: List[int],
5    values: List[int],
6    memo: List[List[int]],
7    remaining_weight: int,
8    n: int,
9) -> int:
10    if n == 0 or remaining_weight == 0:
11        return 0
12    if memo[n][remaining_weight] != -1:
13        return memo[n][remaining_weight]
14    res = 0
15    if weights[n - 1] > remaining_weight:
16        res = knapsack_helper(weights, values, memo, remaining_weight, n - 1)
17    else:
18        res = max(
19            values[n - 1] + knapsack_helper(weights, values, memo, remaining_weight - weights[n - 1], n - 1),
20            knapsack_helper(weights, values, memo, remaining_weight, n - 1),
21        )
22    memo[n][remaining_weight] = res
23    return res
24
25def knapsack(weights: List[int], values: List[int], max_weight: int) -> int:
26    n = len(weights)
27    memo = [[-1 for i in range(max_weight + 1)] for j in range(n + 1)]
28    return knapsack_helper(weights, values, memo, max_weight, n)
29
30if __name__ == "__main__":
31    weights = [int(x) for x in input().split()]
32    values = [int(x) for x in input().split()]
33    max_weight = int(input())
34    res = knapsack(weights, values, max_weight)
35    print(res)
36
1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7    public static int knapsackHelper(List<Integer> weights, List<Integer> values, int[][] memo, int remainingWeight, int n) {
8        if (n == 0 || remainingWeight == 0) {
9            return 0;
10        }
11        if (memo[n][remainingWeight] != -1) {
12            return memo[n][remainingWeight];
13        }
14        int res;
15        if (weights.get(n - 1) > remainingWeight) {
16            res = knapsackHelper(weights, values, memo, remainingWeight, n - 1);
17        } else {
18            res = Math.max(
19                values.get(n - 1) + knapsackHelper(weights, values, memo, remainingWeight - weights.get(n - 1), n - 1),
20                knapsackHelper(weights, values, memo, remainingWeight, n - 1));
21        }
22        return memo[n][remainingWeight] = res;
23    }
24
25    public static int knapsack(List<Integer> weights, List<Integer> values, int maxWeight) {
26        int n = weights.size();
27        int[][] memo = new int[n + 1][maxWeight + 1];
28        for (int i = 0; i < n + 1; i++) {
29            Arrays.fill(memo[i], -1);
30        }
31        return knapsackHelper(weights, values, memo, maxWeight, n);
32    }
33
34    public static List<String> splitWords(String s) {
35        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
36    }
37
38    public static void main(String[] args) {
39        Scanner scanner = new Scanner(System.in);
40        List<Integer> weights = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
41        List<Integer> values = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
42        int maxWeight = Integer.parseInt(scanner.nextLine());
43        scanner.close();
44        int res = knapsack(weights, values, maxWeight);
45        System.out.println(res);
46    }
47}
48
1"use strict";
2
3function knapsackHelper(weights, values, memo, remainingWeight, n) {
4    if (n === 0 || remainingWeight === 0) {
5        return 0;
6    }
7    if (memo[n][remainingWeight] !== -1) {
8        return memo[n][remainingWeight];
9    }
10    let res;
11    if (weights[n - 1] > remainingWeight) {
12        res = knapsackHelper(weights, values, memo, remainingWeight, n - 1);
13    } else {
14        res = Math.max(
15            values[n - 1] + knapsackHelper(weights, values, memo, remainingWeight - weights[n - 1], n - 1),
16            knapsackHelper(weights, values, memo, remainingWeight, n - 1),
17        );
18    }
19    memo[n][remainingWeight] = res;
20    return res;
21}
22function knapsack(weights, values, maxWeight) {
23    const n = weights.length;
24    const memo = new Array(n + 1).fill().map(() => new Array(maxWeight + 1).fill(-1));
25    return knapsackHelper(weights, values, memo, maxWeight, n);
26}
27
28function splitWords(s) {
29    return s === "" ? [] : s.split(" ");
30}
31
32function* main() {
33    const weights = splitWords(yield).map((v) => parseInt(v));
34    const values = splitWords(yield).map((v) => parseInt(v));
35    const maxWeight = parseInt(yield);
36    const res = knapsack(weights, values, maxWeight);
37    console.log(res);
38}
39
40class EOFError extends Error {}
41{
42    const gen = main();
43    const next = (line) => gen.next(line).done && process.exit();
44    let buf = "";
45    next();
46    process.stdin.setEncoding("utf8");
47    process.stdin.on("data", (data) => {
48        const lines = (buf + data).split("\n");
49        buf = lines.pop();
50        lines.forEach(next);
51    });
52    process.stdin.on("end", () => {
53        buf && next(buf);
54        gen.throw(new EOFError());
55    });
56}
57
1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <limits>
5#include <sstream>
6#include <string>
7#include <vector>
8
9int knapsackHelper(std::vector<int>& weights, std::vector<int>& values, std::vector<std::vector<int>>& memo, int remaining_weight, int n) {
10    if (n == 0 || remaining_weight == 0) {
11        return 0;
12    }
13    if (memo[n][remaining_weight] != -1) {
14        return memo[n][remaining_weight];
15    }
16    int res;
17    if (weights[n - 1] > remaining_weight) {
18        res = knapsackHelper(weights, values, memo, remaining_weight, n - 1);
19    } else {
20        res = std::max(
21            values[n - 1] + knapsackHelper(weights, values, memo, remaining_weight - weights[n - 1], n - 1),
22            knapsackHelper(weights, values, memo, remaining_weight, n - 1));
23    }
24    return memo[n][remaining_weight] = res;
25}
26
27int knapsack(std::vector<int>& weights, std::vector<int>& values, int max_weight) {
28    int n = weights.size();
29    std::vector<std::vector<int>> memo(n + 1, std::vector<int>(max_weight + 1, -1));
30    return knapsackHelper(weights, values, memo, max_weight, n);
31}
32
33template<typename T>
34std::vector<T> get_words() {
35    std::string line;
36    std::getline(std::cin, line);
37    std::istringstream ss{line};
38    ss >> std::boolalpha;
39    std::vector<T> v;
40    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
41    return v;
42}
43
44void ignore_line() {
45    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
46}
47
48int main() {
49    std::vector<int> weights = get_words<int>();
50    std::vector<int> values = get_words<int>();
51    int max_weight;
52    std::cin >> max_weight;
53    ignore_line();
54    int res = knapsack(weights, values, max_weight);
55    std::cout << res << '\n';
56}
57

The time and space complexity will be O(n * w) where n is the number of items and w is the max weight because we have O(n * w) states and the time complexity of computing each state is O(1). Similarly, the only additional memory we use is an n * w array, so the space complexity is O(n * w).

Bottom-up DP

This can even be done iteratively. This is similar to the recursive version, except instead of going from top-down, we build our solution from the bottom-up. Here is the iterative implementation:

1from typing import List
2
3def knapsack(weights: List[int], values: List[int], max_weight: int) -> int:
4    n = len(weights)
5    # 2D dp array, where max_value[i][j] is the maximum knapsack value when
6    # considering the first i items with a max weight capacity of j
7    max_value = [[0 for i in range(max_weight + 1)] for j in range(n + 1)]
8    # iterate through all items
9    for i in range(n + 1):
10        # and all possible available weights
11        for w in range(max_weight + 1):
12            if i == 0 or w == 0:
13                # if we consider no items or no weight, the max value is 0
14                max_value[i][w] = 0
15            elif w < weights[i - 1]:
16                # if the weight of the current item exceeds the max available weight,
17                # then the answer is the max value when considering the first i - 1 items
18                max_value[i][w] = max_value[i - 1][w]
19            else:
20                # otherwise, we choose the best option between either:
21                # picking up: item's value + max value when considering the rest of the items and a new weight
22                # giving up: similar to the condition above
23                max_value[i][w] = max(
24                    values[i - 1] + max_value[i - 1][w - weights[i - 1]],
25                    max_value[i - 1][w],
26                )
27    # the answer is the max value when considering all n items and available weight of max_weight
28    return max_value[n][max_weight]
29
30if __name__ == "__main__":
31    weights = [int(x) for x in input().split()]
32    values = [int(x) for x in input().split()]
33    max_weight = int(input())
34    res = knapsack(weights, values, max_weight)
35    print(res)
36
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 remainingWeight) {
8        int n = weights.size();
9        // 2D dp array, where maxValue[i][j] is the maximum knapsack value when
10        // considering the first i items with a max weight capacity of j
11        int[][] maxValue = new int[n + 1][remainingWeight + 1];
12        // iterate through all items
13        for (int i = 0; i <= n; i++) {
14            // and all possible available weights
15            for (int w = 0; w <= remainingWeight; w++) {
16                if (i == 0 || w == 0) {
17                    // if we consider no items or no weight, the max value is 0
18                    maxValue[i][w] = 0;
19                } else if (w < weights.get(i - 1)) {
20                    // if the weight of the current item exceeds the max available weight,
21                    // then the answer is the max value when considering the first i - 1 items
22                    maxValue[i][w] = maxValue[i - 1][w];
23                } else {
24                    // otherwise, we choose the best option between either:
25                    // picking up: item's value + max value when considering the rest of the items and a new weight
26                    // giving up: similar to the condition above
27                    maxValue[i][w] = Math.max(
28                        values.get(i - 1) + maxValue[i - 1][w - weights.get(i - 1)],
29                        maxValue[i - 1][w]);
30                }
31            }
32        }
33        // the answer is the max value when considering all n items and available weight of max_weight
34        return maxValue[n][remainingWeight];
35    }
36
37    public static List<String> splitWords(String s) {
38        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
39    }
40
41    public static void main(String[] args) {
42        Scanner scanner = new Scanner(System.in);
43        List<Integer> weights = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
44        List<Integer> values = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
45        int maxWeight = Integer.parseInt(scanner.nextLine());
46        scanner.close();
47        int res = knapsack(weights, values, maxWeight);
48        System.out.println(res);
49    }
50}
51
1"use strict";
2
3function knapsack(weights, values, remainingWeight) {
4    const n = weights.length;
5    // 2D dp array, where maxValue[i][j] is the maximum knapsack value when
6    // considering the first i items with a max weight capacity of j
7    const maxValue = new Array(n + 1);
8    for (let i = 0; i <= n; i++) {
9        maxValue[i] = new Array(remainingWeight + 1).fill(0);
10    }
11    // iterate through all items
12    for (let i = 0; i <= n; i++) {
13        // and all possible available weights
14        for (let w = 0; w <= remainingWeight; w++) {
15            if (i === 0 || w === 0) {
16                // if we consider no items or no weight, the max value is 0
17                maxValue[i][w] = 0;
18            } else if (w < weights[i - 1]) {
19                // if the weight of the current item exceeds the max available weight,
20                // then the answer is the max value when considering the first i - 1 items
21                maxValue[i][w] = maxValue[i - 1][w];
22            } else {
23                // otherwise, we choose the best option between either:
24                // picking up: item's value + max value when considering the rest of the items and a new weight
25                // giving up: similar to the condition above
26                maxValue[i][w] = Math.max(
27                    values[i - 1] + maxValue[i - 1][w - weights[i - 1]],
28                    maxValue[i - 1][w],
29                );
30            }
31        }
32    }
33    // the answer is the max value when considering all n items and available weight of max_weight
34    return maxValue[n][remainingWeight];
35}
36
37function splitWords(s) {
38    return s === "" ? [] : s.split(" ");
39}
40
41function* main() {
42    const weights = splitWords(yield).map((v) => parseInt(v));
43    const values = splitWords(yield).map((v) => parseInt(v));
44    const maxWeight = parseInt(yield);
45    const res = knapsack(weights, values, maxWeight);
46    console.log(res);
47}
48
49class EOFError extends Error {}
50{
51    const gen = main();
52    const next = (line) => gen.next(line).done && process.exit();
53    let buf = "";
54    next();
55    process.stdin.setEncoding("utf8");
56    process.stdin.on("data", (data) => {
57        const lines = (buf + data).split("\n");
58        buf = lines.pop();
59        lines.forEach(next);
60    });
61    process.stdin.on("end", () => {
62        buf && next(buf);
63        gen.throw(new EOFError());
64    });
65}
66
1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <limits>
5#include <sstream>
6#include <string>
7#include <vector>
8
9int knapsack(std::vector<int>& weights, std::vector<int>& values, int max_weight) {
10    int n = weights.size();
11    // 2D dp array, where max_value[i][j] is the maximum knapsack value when
12    // considering the first i items with a max weight capacity of j
13    std::vector<std::vector<int>> max_value(n + 1, std::vector<int>(max_weight + 1));
14    // iterate through all items
15    for (int i = 0; i <= n; i++) {
16        // and all possible available weights
17        for (int w = 0; w <= max_weight; w++) {
18            if (i == 0 || w == 0) {
19                // if we consider no items or no weight, the max value is 0
20                max_value[i][w] = 0;
21            } else if (w < weights[i - 1]) {
22                // if the weight of the current item exceeds the max available weight,
23                // then the answer is the max value when considering the first i - 1 items
24                max_value[i][w] = max_value[i - 1][w];
25            } else {
26                // otherwise, we choose the best option between either:
27                // picking up: item's value + max value when considering the rest of the items and a new weight
28                // giving up: similar to the condition above
29                max_value[i][w] = std::max(
30                    values[i - 1] + max_value[i - 1][w - weights[i - 1]],
31                    max_value[i - 1][w]);
32            }
33        }
34    }
35    // the answer is the max value when considering all n items and available weight of max_weight
36    return max_value[n][max_weight];
37}
38
39template<typename T>
40std::vector<T> get_words() {
41    std::string line;
42    std::getline(std::cin, line);
43    std::istringstream ss{line};
44    ss >> std::boolalpha;
45    std::vector<T> v;
46    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
47    return v;
48}
49
50void ignore_line() {
51    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
52}
53
54int main() {
55    std::vector<int> weights = get_words<int>();
56    std::vector<int> values = get_words<int>();
57    int max_weight;
58    std::cin >> max_weight;
59    ignore_line();
60    int res = knapsack(weights, values, max_weight);
61    std::cout << res << '\n';
62}
63

For an intuitive explanation, consider the recursive version again. If we were to translate it to an iterative version while maintaining the same recurrence, we need to build our solution from the bottom-up since maxValue[i][w] depends on the values in the previous row maxValue[i - 1]. Also, since the weights for the items are arbitrary, we will need to calculate the maximum value for all weights from 0 to max_weight to ensure we have the answer for the recurrence, since maxValue[i][w] depends on maxValue[i - 1][w - weights[i - 1]] where 0 <= weights[i - 1] <= w.

First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide

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.

First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
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
1"use strict";
2
3function knapsack(weights, values, maxWeight) {
4    // initialize the dp array and set values to -1 except for index 0
5    const dp = Array(maxWeight + 1).fill(-1);
6    dp[0] = 0;
7    // loop through the objects
8    for (let i = 0; i < weights.length; i++) {
9        // loop through the dp indexes from largest value to smallest value
10        for (let j = maxWeight; j >= weights[i]; j--) {
11            // check if we have reached the weight value before
12            if (dp[j - weights[i]] !== -1) {
13                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
14            }
15        }
16    }
17    return Math.max(...dp);
18}
19
20function splitWords(s) {
21    return s === "" ? [] : s.split(" ");
22}
23
24function* main() {
25    const weights = splitWords(yield).map((v) => parseInt(v));
26    const values = splitWords(yield).map((v) => parseInt(v));
27    const maxWeight = parseInt(yield);
28    const res = knapsack(weights, values, maxWeight);
29    console.log(res);
30}
31
32class EOFError extends Error {}
33{
34    const gen = main();
35    const next = (line) => gen.next(line).done && process.exit();
36    let buf = "";
37    next();
38    process.stdin.setEncoding("utf8");
39    process.stdin.on("data", (data) => {
40        const lines = (buf + data).split("\n");
41        buf = lines.pop();
42        lines.forEach(next);
43    });
44    process.stdin.on("end", () => {
45        buf && next(buf);
46        gen.throw(new EOFError());
47    });
48}
49
1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <limits>
5#include <sstream>
6#include <string>
7#include <vector>
8
9int knapsack(std::vector<int>& weights, std::vector<int>& values, int max_weight) {
10    // initialize the dp array and set values to -1 except for index 0
11    std::vector<int> dp(max_weight + 1, -1);
12    dp[0] = 0;
13    // loop through every object which is simply length of weights array, values array also works as they should be same length
14    for (int i = 0; i < weights.size(); i++) {
15        // as discussed make sure to loop from highest value backwards to avoid reusing the same object
16        for (int j = max_weight; j >= weights[i]; j--) {
17            // if we establish a particular weight is achievable we update out current weight maximum value
18            if (dp[j - weights[i]] != -1) {
19                dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);
20            }
21        }
22    }
23    return *std::max_element(dp.begin(), dp.end());
24}
25
26template<typename T>
27std::vector<T> get_words() {
28    std::string line;
29    std::getline(std::cin, line);
30    std::istringstream ss{line};
31    ss >> std::boolalpha;
32    std::vector<T> v;
33    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
34    return v;
35}
36
37void ignore_line() {
38    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
39}
40
41int main() {
42    std::vector<int> weights = get_words<int>();
43    std::vector<int> values = get_words<int>();
44    int max_weight;
45    std::cin >> max_weight;
46    ignore_line();
47    int res = knapsack(weights, values, max_weight);
48    std::cout << res << '\n';
49}
50

Time Complexity: O(n * max_weight)
Space Complexity: O(n * max_weight)

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro
Favorite (idle)