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 objectsvalues: an array of integers that denote the values of objectsmax_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)
311import 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}
461"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}
571#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}
57DFS + 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)
361import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7 public