What is optimal substructure?

What are subsctructures?

A substructure is simply a subpart of a bigger structure.

For example, we want to make a big Lego tower using Lego bricks. We can do that by stacking the small Lego towers on top of each other. Each Lego tower is a substructure, and one bigger tower is the bigger structure.

Let’s consider a binary tree where each node can have a maximum of two child nodes. Multiple sub-root nodes are substructures and can be combined to form a larger tree.

Please look at the following example to understand substructures.

Optimal substructure

Optimal substructure means that we combine the optimal results of subproblems to achieve the optimal result of the bigger problem.

Substructures in dynamic programming

Dynamic programming is a way to solve complex problems by breaking them down into smaller problems with an optimal solution. It combines these solutions to evaluate the optimal solution of the complete problem.

Let’s look at the 0/1 knapsack problem and how we can use optimal substructure property to solve the problem.

0/1 knapsack

Suppose you have a list of weights and corresponding values for n items. You have a knapsack that can carry items up to a specific maximum weight, known as the capacity of the knapsack.

You want to maximize the sum of values of the items in your knapsack while ensuring that the sum of the weights of the items remains less than or equal to the knapsack’s capacity.

Solution

For example, we have the following list of values and weights with the capacity of $5$ :

values: $[3, 5, 2, 7]$
weights: $[3, 1, 2, 4]$

To find the maximum value, we try all the possible combinations:

$3 + 5$ (total weight $4$ ) $= 8$
$3 + 2$ (total weight $5$ ) $= 5$
$5 + 2$ (total weight $3$ ) $= 7$
$5 + 7$ (total weight $5$ ) $= 12$

Here, we divide the problem into subproblems, and for each item, if its weight is less than the capacity, we check whether we should place it in the knapsack.

Example: Dynamic programming approach which stores the results of subproblems

Using dynamic programming we will use a 2-D table to store the total values corresponding to capacity of the knapsack. We will store the optimal solution of the trivial substructures and use them to solve complex structure. The stored value can be retrieved from the table in $O(1)$ , thus reducing the overall time complexity. In this scenario the trivial substructure is when the capacity of the knapsack is $1$ and we have to decide which item to include to have maximum value.

The following code implements the concept mentioned above:

def find_knapsack(capacity, weights, values, n):
    dp = [[-1 for i in range(capacity + 1)] for j in range(n + 1)]
    return find_knapsack_value(capacity, weights, values, n, dp)
def find_knapsack_value(capacity, weights, values, n, dp):
    # Base case
    if n == 0 or capacity == 0:
        return 0
    
    #If we have solved it earlier, then return the result from memory
    if dp[n][capacity] != -1:
        return dp[n][capacity]
 
    #Otherwise, we solve it for the new combination and save the results in the memory
    if weights[n-1] <= capacity:
        dp[n][capacity] = max(
            values[n-1] + find_knapsack_value(capacity-weights[n-1], weights, values, n-1, dp),
            find_knapsack_value(capacity, weights, values, n-1, dp)
            )
        return dp[n][capacity]
    dp[n][capacity] = find_knapsack_value(capacity, weights, values, n-1, dp)
    return dp[n][capacity] 
# Driver code
def main():
    weights = [1, 2, 3, 5]
    values = [1, 5, 4, 8]
    capacity = 6
    n = 4
    print("We have a knapsack of capacity ",capacity, " and we are given the following list of item values and weights:", sep="")
    print("-"*30, sep="")
    print("{:<10}{:<5}{:<5}".format("Weights", "|", "Values"))
    print("-"*30)
    for j in range(len(values)):
        print("{:<10}{:<5}{:<5}".format(weights[j], "|", values[j]))
    result = find_knapsack(capacity, weights, values, n)
    print("\nThe maximum we can earn is: ", result, sep="")
if __name__ == '__main__':
    main()

0/1 Knapsack solved using dynamic programming

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources