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
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.
1// helper function that returns the maximum value when considering2// the first n items and remaining available weight remaining_weight3intknapsackHelper(std::vector<int> weights, std::vector<int> values, int remaining_weight, int n){
4// base case: if there are no items or no available weight in the knapsack to use, the maximum value is 05if (n == 0 || remaining_weight == 0) {
6return0;
7 }
8// if the weight of the current item exceeds the available weight, 9// skip the current item and process the next one10if (weights[n - 1] > remaining_weight) {
11returnknapsackHelper(weights, values, remaining_weight, n - 1);
12 }
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 items15// (2) give up the current item: maximum value with the rest of the items16return std::max(
17 values[n - 1] + knapsackHelper(weights, values, remaining_weight - weights[n - 1], n - 1),
18knapsackHelper(weights, values, remaining_weight, n - 1));
19}
20intknapsack(std::vector<int> weights, std::vector<int> values, int max_weight){
21int n = weights.size();
22returnknapsackHelper(weights, values, max_weight, n);
23}
24
1// helper function that returns the maximum value when considering2// the first n items and remaining available weight remainingWeight3publicstaticintknapsackHelper(List<Integer> weights, List<Integer> values, int remainingWeight, int n){
4// base case: if there are no items or no available weight in the knapsack to use, the maximum value is 05if (n == 0 || remainingWeight == 0) {
6return0;
7 }
8// if the weight of the current item exceeds the available weight, 9// skip the current item and process the next one10if (weights.get(n - 1) > remainingWeight) {
11return knapsackHelper(weights, values, remainingWeight, n - 1);
12 }
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 items15// (2) give up the current item: maximum value with the rest of the items16return Math.max(
17 values.get(n - 1) + knapsackHelper(weights, values, remainingWeight - weights.get(n - 1), n - 1),
18 knapsackHelper(weights, values, remainingWeight, n - 1));
19}
2021publicstaticintknapsack(List<Integer> weights, List<Integer> values, int maxWeight){
22int n = weights.size();
23return knapsackHelper(weights, values, maxWeight, n);
24}
25
1# helper function that returns the maximum value when considering2# the first n items and remaining available weight remaining_weight3defknapsack_helper(weights: List[int], values: List[int], remaining_weight: int, n: int) -> int:4# base case: if there are no items or no available weight in the knapsack to use, the maximum value is 05if n == 0or remaining_weight == 0:
6return07# if the weight of the current item exceeds the available weight, 8# skip the current item and process the next one9if weights[n - 1] > remaining_weight:
10return knapsack_helper(weights, values, remaining_weight, n - 1)
11# recurrence relation: choose the maximum of two possibilities:12# (1) pick up the current item: current value + maximum value with the rest of the items13# (2) give up the current item: maximum value with the rest of the items14returnmax(values[n - 1] + knapsack_helper(weights, values, remaining_weight - weights[n - 1], n - 1),
15 knapsack_helper(weights, values, remaining_weight, n - 1))
1617defknapsack(weights: List[int], values: List[int], max_weight: int) -> int:18 n = len(weights)
19return knapsack_helper(weights, values, max_weight, n)
20
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.
1
-
1intknapsackHelper(std::vector<int> weights, std::vector<int> values, int remaining_weight, int n){
1
+
1intknapsackHelper(std::vector<int> weights, std::vector<int> values, std::vector<std::vector<int>> memo, int remaining_weight, int n){
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:
1intknapsack(std::vector<int> weights, std::vector<int> values, int max_weight){
2int n = weights.size();
3// 2D dp array, where maxValue[i][j] is the maximum knapsack value when4// considering the first i items with a max weight capacity of j5int maxValue[n + 1][max_weight + 1];
6// iterate through all items7for (int i = 0; i <= n; i++) {
8// and all possible available weights9for (int w = 0; w <= max_weight; w++) {
10// if we consider no items or no weight, the max value is 011if (i == 0 || w == 0) {
12 maxValue[i][w] = 0;
13// if the weight of the current item exceeds the max available weight,14// then the answer is the max value when considering the first i - 1 items15 } elseif (w < weights[i - 1]) {
16 maxValue[i][w] = maxValue[i - 1][w];
17// otherwise, we choose the best option between either:18// picking up: item's value + max value when considering the rest of the items and a new weight19// giving up: similar to the condition above20 } else {
21 maxValue[i][w] = std::max(values[i - 1] + maxValue[i - 1][w - weights[i - 1]],
22 maxValue[i - 1][w]);
23 }
24 }
25 }
26// the answer is the max value when considering all n items and available weight of max_weight27return maxValue[n][max_weight];
28}
29
1publicstaticintknapsack(List<Integer> weights, List<Integer> values, int remainingWeight){
2int n = weights.size();
3// 2D dp array, where maxValue[i][j] is the maximum knapsack value when4// considering the first i items with a max weight capacity of j5int[][] maxValue = newint[n + 1][remainingWeight + 1];
6// iterate through all items7for (int i = 0; i <= n; i++) {
8// and all possible available weights9for (int w = 0; w <= remainingWeight; w++) {
10// if we consider no items or no weight, the max value is 011if (i == 0 || w == 0) {
12 maxValue[i][w] = 0;
13// if the weight of the current item exceeds the max available weight,14// then the answer is the max value when considering the first i - 1 items15 } elseif (w < weights.get(i - 1)) {
16 maxValue[i][w] = maxValue[i - 1][w];
17// otherwise, we choose the best option between either:18// picking up: item's value + max value when considering the rest of the items and a new weight19// giving up: similar to the condition above20 } else {
21 maxValue[i][w] = Math.max(values.get(i - 1) + maxValue[i - 1][w - weights.get(i - 1)],
22 maxValue[i - 1][w]);
23 }
24 }
25 }
26// the answer is the max value when considering all n items and available weight of max_weight27return maxValue[n][remainingWeight];
28}
29
1defknapsack(weights: List[int], values: List[int], max_weight: int) -> int:2 n = len(weights)
3# 2D dp array, where maxValue[i][j] is the maximum knapsack value when4# considering the first i items with a max weight capacity of j5 max_value = [[0] * (max_weight + 1)] * (n + 1)
6# iterate through all items7for i inrange(n + 1):
8# and all possible available weights9for w inrange(max_weight + 1):
10# if we consider no items or no weight, the max value is 011if i == 0or w == 0:
12 max_value[i][w] = 013# if the weight of the current item exceeds the max available weight,14# then the answer is the max value when considering the first i - 1 items15elif w < weights[i - 1]:
16 max_value[i][w] = max_value[i - 1][w]
17# otherwise, we choose the best option between either:18# picking up: item's value + max value when considering the rest of the items and a new weight19# giving up: similar to the condition above20else:
21 max_value[i][w] = max(values[i - 1] + max_value[i - 1][w - weights[i - 1]],
22 max_value[i - 1][w])
23# the answer is the max value when considering all n items and available weight of max_weight24return max_value[n][max_weight]
25
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 .
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 importList23defknapsack(weights: List[int], values: List[int], max_weight: int) -> int:4# initialize the array and set values to -1 except for index 05 dp = [-1] * (max_weight + 1)
6 dp[0] = 07# loop through the objects8for i inrange(len(weights)):
9# loop through the dp indexes from largest value to smallest one10for j inrange(max_weight, weights[i] - 1, -1):
11# check if we have reached the weight value before12if dp[j - weights[i]] != -1:
13 dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
14returnmax(dp)
1516if __name__ == '__main__':
17 weights = [int(x) for x ininput().split()]
18 values = [int(x) for x ininput().split()]
19 max_weight = int(input())
20 res = knapsack(weights, values, max_weight)
21print(res)
22
1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
56classSolution{
7publicstaticintknapsack(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 09int [] dp = newint[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 length13for (int i = 0; i < weights.size(); i++) {
14// as discussed make sure to loop from highest value backwards to avoid reusing the same object15for (int j = maxWeight; j >= weights.get(i); j--) {
16// if we establish a particular weight is achievable we update out current weight maximum value17if(dp[j - weights.get(i)] != -1) {
18 dp[j] = Math.max(dp[j], dp[j - weights.get(i)] + values.get(i));
19 }
20 }
21 }
22int maxValue = -1;
23for (int i = 0; i < maxWeight + 1; i++) {
24 maxValue = Math.max(maxValue, dp[i]);
25 }
26return maxValue;
27 }
2829publicstatic List<String> splitWords(String s){
30return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
31 }
3233publicstaticvoidmain(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());
37int maxWeight = Integer.parseInt(scanner.nextLine());
38 scanner.close();
39int res = knapsack(weights, values, maxWeight);
40 System.out.println(res);
41 }
42}
43
1functionknapsack(weights, values, maxWeight) {
2// initialize the dp array and set values to -1 except for index 03const dp = Array(maxWeight + 1).fill(-1);
4 dp[0] = 0;
5// loop through the objects6for (let i = 0; i < weights.length; i++) {
7// loop through the dp indexes from largest value to smallest value8for (let j = maxWeight; j >= weights[i]; j--) {
9// check if we have reached the weight value before10if (dp[j - weights[i]] !== -1) {
11 dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
12 }
13 }
14 }
15returnMath.max(...dp);
16}
1718functionsplitWords(s) {
19return s == "" ? [] : s.split(' ');
20}
2122function* main() {
23const weights = splitWords(yield).map((v) =>parseInt(v));
24const values = splitWords(yield).map((v) =>parseInt(v));
25const maxWeight = parseInt(yield);
26const res = knapsack(weights, values, maxWeight);
27console.log(res);
28}
2930classEOFErrorextendsError{}
31{
32const gen = main();
33const next = (line) => gen.next(line).done && process.exit();
34let buf = '';
35 next();
36 process.stdin.setEncoding('utf8');
37 process.stdin.on('data', (data) => {
38const lines = (buf + data).split('\n');
39 buf = lines.pop();
40 lines.forEach(next);
41 });
42 process.stdin.on('end', () => {
43 buf && next(buf);
44 gen.throw(new EOFError());
45 });
46}
47