0/1 Knapsack Practice Problem
Let's apply the 0/1 knapsack pattern with a practical example.
Given n items where item i has weight weights[i] and value values[i], find the maximum total value achievable without exceeding capacity max_weight. Each item can be selected at most once.
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
Approach
This is a direct application of the 0/1 knapsack pattern. The state dp[i][j] represents the maximum value using the first i items with capacity j. For each item, we choose between skipping it or including it:
dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight] + value)
The decision tree below shows all possibilities. Each left branch represents taking an item, each right branch represents skipping it:
The path yielding value 9 (taking items with weights 3 and 4) is optimal.
Brute Force
A recursive approach tries all 2^n subsets:
1# helper function that returns the maximum value when considering
2# the first n items and remaining available weight remaining_weight
3def knapsack_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 0
5 if n == 0 or remaining_weight == 0:
6 return 0
7 # if the weight of the current item exceeds the available weight,
8 # skip the current item and process the next one
9 if weights[n - 1] > remaining_weight:
10 return 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 items
13 # (2) give up the current item: maximum value with the rest of the items
14 return max(
15 values[n - 1] + knapsack_helper(weights, values, remaining_weight - weights[n - 1], n - 1),
16 knapsack_helper(weights, values, remaining_weight, n - 1),
17 )
18
19def knapsack(weights: list[int], values: list[int], max_weight: int) -> int:
20 n = len(weights)
21 return knapsack_helper(weights, values, max_weight, n)
22
23if __name__ == "__main__":
24 weights = [int(x) for x in input().split()]
25 values = [int(x) for x in input().split()]
26 max_weight = int(input())
27 res = knapsack(weights, values, max_weight)
28 print(res)
291import 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}
571function knapsackHelper(weights: number[], values: number[], remainingWeight: number, n: number): number {
2 if (n === 0 || remainingWeight === 0) {
3 return 0;
4 }
5 if (weights[n - 1] > remainingWeight) {
6 return knapsackHelper(weights, values, remainingWeight, n - 1);
7 }
8 return Math.max(
9 values[n - 1] + knapsackHelper(weights, values, remainingWeight - weights[n - 1], n - 1),
10 knapsackHelper(weights, values, remainingWeight, n - 1),
11 );
12}
13function knapsack(weights: number[], values: number[], maxWeight: number): number {
14 const n = weights.length;
15 return knapsackHelper(weights, values, maxWeight, n);
16}
17
18function splitWords(s: string): string[] {
19 return s === "" ? [] : s.split(" ");
20}
21
22function* main() {
23 const weights = splitWords(yield).map((v) => parseInt(v));
24 const values = splitWords(yield).map((v) => parseInt(v));
25 const maxWeight = parseInt(yield);
26 const res = knapsack(weights, values, maxWeight);
27 console.log(res);
28}
29
30class EOFError extends Error {}
31{
32 const gen = main();
33 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
34 let buf = "";
35 next();
36 process.stdin.setEncoding("utf8");
37 process.stdin.on("data", (data) => {
38 const 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}
471#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}
57Memoization
The brute force has overlapping subproblems. Adding memoization avoids recomputation by storing results in dp[n][remaining_weight]:
1def knapsack_helper(
2 weights: list[int],
3 values: list[int],
4 memo: list[list[int]],
5 remaining_weight: int,
6 n: int,
7) -> int:
8 if n == 0 or remaining_weight == 0:
9 return 0
10 if memo[n][remaining_weight] != -1:
11 return memo[n][remaining_weight]
12 res = 0
13 if weights[n - 1] > remaining_weight:
14 res = knapsack_helper(weights, values, memo, remaining_weight, n - 1)
15 else:
16 res = max(
17 values[n - 1] + knapsack_helper(weights, values, memo, remaining_weight - weights[n - 1], n - 1),
18 knapsack_helper(weights, values, memo, remaining_weight, n - 1),
19 )
20 memo[n][remaining_weight] = res
21 return res
22
23def knapsack(weights: list[int], values: list[int], max_weight: int) -> int:
24 n = len(weights)
25 memo = [[-1 for i in range(max_weight + 1)] for j in range(n + 1)]
26 return knapsack_helper(weights, values, memo, max_weight, n)
27
28if __name__ == "__main__":
29 weights = [int(x) for x in input().split()]
30 values = [int(x) for x in input().split()]
31 max_weight = int(input())
32 res = knapsack(weights, values, max_weight)
33 print(res)
341import 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}
481"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}
571function knapsackHelper(weights: number[], values: number[], memo: number[][], remainingWeight: number, n: number): number {
2 if (n === 0 || remainingWeight === 0) {
3 return 0;
4 }
5 if (memo[n][remainingWeight] !== -1) {
6 return memo[n][remainingWeight];
7 }
8 let res;
9 if (weights[n - 1] > remainingWeight) {
10 res = knapsackHelper(weights, values, memo, remainingWeight, n - 1);
11 } else {
12 res = Math.max(
13 values[n - 1] + knapsackHelper(weights, values, memo, remainingWeight - weights[n - 1], n - 1),
14 knapsackHelper(weights, values, memo, remainingWeight, n - 1),
15 );
16 }
17 memo[n][remainingWeight] = res;
18 return res;
19}
20function knapsack(weights: number[], values: number[], maxWeight: number): number {
21 const n = weights.length;
22 const memo = new Array(n + 1).fill(0).map(() => new Array(maxWeight + 1).fill(-1));
23 return knapsackHelper(weights, values, memo, maxWeight, n);
24}
25
26function splitWords(s: string): string[] {
27 return s === "" ? [] : s.split(" ");
28}
29
30function* main() {
31 const weights = splitWords(yield).map((v) => parseInt(v));
32 const values = splitWords(yield).map((v) => parseInt(v));
33 const maxWeight = parseInt(yield);
34 const res = knapsack(weights, values, maxWeight);
35 console.log(res);
36}
37
38class EOFError extends Error {}
39{
40 const gen = main();
41 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
42 let buf = "";
43 next();
44 process.stdin.setEncoding("utf8");
45 process.stdin.on("data", (data) => {
46 const lines = (buf + data).split("\n");
47 buf = lines.pop() ?? "";
48 lines.forEach(next);
49 });
50 process.stdin.on("end", () => {
51 buf && next(buf);
52 gen.throw(new EOFError());
53 });
54}
551#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}
57Time and space complexity: O(n × max_weight) for both, since we have that many states and each takes O(1) to compute.
Bottom-up DP
Converting to iterative form, we fill a 2D table row by row:
1def knapsack(weights: list[int], values: list[int], max_weight: int) -> int:
2 n = len(weights)
3 # 2D dp array, where max_value[i][j] is the maximum knapsack value when
4 # considering the first i items with a max weight capacity of j
5 max_value = [[0 for i in range(max_weight + 1)] for j in range(n + 1)]
6 # iterate through all items
7 for i in range(n + 1):
8 # and all possible available weights
9 for w in range(max_weight + 1):
10 if i == 0 or w == 0:
11 # if we consider no items or no weight, the max value is 0
12 max_value[i][w] = 0
13 elif w < weights[i - 1]:
14 # if the weight of the current item exceeds the max available weight,
15 # then the answer is the max value when considering the first i - 1 items
16 max_value[i][w] = max_value[i - 1][w]
17 else:
18 # otherwise, we choose the best option between either:
19 # picking up: item's value + max value when considering the rest of the items and a new weight
20 # giving up: similar to the condition above
21 max_value[i][w] = max(
22 values[i - 1] + max_value[i - 1][w - weights[i - 1]],
23 max_value[i - 1][w],
24 )
25 # the answer is the max value when considering all n items and available weight of max_weight
26 return max_value[n][max_weight]
27
28if __name__ == "__main__":
29 weights = [int(x) for x in input().split()]
30 values = [int(x) for x in input().split()]
31 max_weight = int(input())
32 res = knapsack(weights, values, max_weight)
33 print(res)
341import 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}
511"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}
661function knapsack(weights: number[], values: number[], remainingWeight: number): number {
2 const n = weights.length;
3 const maxValue = new Array(n + 1);
4 for (let i = 0; i <= n; i++) {
5 maxValue[i] = new Array(remainingWeight + 1).fill(0);
6 }
7 for (let i = 0; i <= n; i++) {
8 for (let w = 0; w <= remainingWeight; w++) {
9 if (i === 0 || w === 0) {
10 maxValue[i][w] = 0;
11 } else if (w < weights[i - 1]) {
12 maxValue[i][w] = maxValue[i - 1][w];
13 } else {
14 maxValue[i][w] = Math.max(
15 values[i - 1] + maxValue[i - 1][w - weights[i - 1]],
16 maxValue[i - 1][w],
17 );
18 }
19 }
20 }
21 return maxValue[n][remainingWeight];
22}
23
24function splitWords(s: string): string[] {
25 return s === "" ? [] : s.split(" ");
26}
27
28function* main() {
29 const weights = splitWords(yield).map((v) => parseInt(v));
30 const values = splitWords(yield).map((v) => parseInt(v));
31 const maxWeight = parseInt(yield);
32 const res = knapsack(weights, values, maxWeight);
33 console.log(res);
34}
35
36class EOFError extends Error {}
37{
38 const gen = main();
39 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
40 let buf = "";
41 next();
42 process.stdin.setEncoding("utf8");
43 process.stdin.on("data", (data) => {
44 const lines = (buf + data).split("\n");
45 buf = lines.pop() ?? "";
46 lines.forEach(next);
47 });
48 process.stdin.on("end", () => {
49 buf && next(buf);
50 gen.throw(new EOFError());
51 });
52}
531#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}
63The table fills from smaller subproblems to larger ones. Each cell depends only on the previous row:
Space Optimization
Since each row only uses the previous row, we reduce to a 1D array by iterating capacities right-to-left. This ensures dp[j - weight] still holds the previous row's value when we update dp[j].
1def knapsack(weights: list[int], values: list[int], max_weight: int) -> int:
2 # initialize the array and set values to -1 except for index 0
3 dp = [-1] * (max_weight + 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(max_weight, 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 max(dp)
13
14if __name__ == "__main__":
15 weights = [int(x) for x in input().split()]
16 values = [int(x) for x in input().split()]
17 max_weight = int(input())
18 res = knapsack(weights, values, max_weight)
19 print(res)
201import 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}
431"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}
491function knapsack(weights: number[], values: number[], remainingWeight: number): number {
2 const n = weights.length;
3 const maxValue = new Array(n + 1);
4 for (let i = 0; i <= n; i++) {
5 maxValue[i] = new Array(remainingWeight + 1).fill(0);
6 }
7 for (let i = 0; i <= n; i++) {
8 for (let w = 0; w <= remainingWeight; w++) {
9 if (i === 0 || w === 0) {
10 maxValue[i][w] = 0;
11 } else if (w < weights[i - 1]) {
12 maxValue[i][w] = maxValue[i - 1][w];
13 } else {
14 maxValue[i][w] = Math.max(
15 values[i - 1] + maxValue[i - 1][w - weights[i - 1]],
16 maxValue[i - 1][w],
17 );
18 }
19 }
20 }
21 return maxValue[n][remainingWeight];
22}
23
24function splitWords(s: string): string[] {
25 return s === "" ? [] : s.split(" ");
26}
27
28function* main() {
29 const weights = splitWords(yield).map((v) => parseInt(v));
30 const values = splitWords(yield).map((v) => parseInt(v));
31 const maxWeight = parseInt(yield);
32 const res = knapsack(weights, values, maxWeight);
33 console.log(res);
34}
35
36class EOFError extends Error {}
37{
38 const gen = main();
39 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
40 let buf = "";
41 next();
42 process.stdin.setEncoding("utf8");
43 process.stdin.on("data", (data) => {
44 const lines = (buf + data).split("\n");
45 buf = lines.pop() ?? "";
46 lines.forEach(next);
47 });
48 process.stdin.on("end", () => {
49 buf && next(buf);
50 gen.throw(new EOFError());
51 });
52}
531#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}
50Time Complexity: O(n × max_weight)
Space Complexity: O(max_weight)