All mock tests are FREE till 31 December — register to save your progress
Unit 7 · Data Structures and Algorithms Paper 2 CS · June 2024 Re-Exam

Arrange the following steps in the correct order to solve the Knapsack problem using Dynamic Programming.
(A) Define the base case when the capacity is zero or no items are left to consider
(B) Compute the maximum value that can be obtained using items up to the i-th item and a knapsack capacity of W
(C) Identify subproblems and their dependencies based on item weights and values
(D) Initialize a table to store results of subproblems
(E) Iterate through each item and each possible capacity to fill the table
Choose the correct answer from the options given below:

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. (A), (C), (D), (E), (B)

Explanation

The keyed order is: fix the base case (capacity 0 or no items), identify the sub-problems and the recurrence, initialise the DP table, iterate over items and capacities to fill it, and read off the maximum value. (Many textbooks list 'identify sub-problems' before the base case, but the base case and recurrence are defined together before the table is filled.)

More Data Structures and Algorithms questions