Module 2: Fundamental Algorithmic Strategies

Brute-Force

Brute force approach

A brute force approach is an approach that finds all the possible solutions to find a
satisfactory solution to a given problem. The brute force algorithm tries out all the
possibilities till a satisfactory solution is not found.

• Many problems solved in day-to-day life using the brute force strategy, for example
exploring all the paths to a nearby market to find the minimum shortest path.
• Arranging the books in a rack using all the possibilities to optimize the rack spaces,
etc.

Such an algorithm can be of two types:

o Optimizing: In this case, the best solution is found. To find the best solution, it
may either find all the possible solutions to find the best solution or if the value of
the best solution is known, it stops finding when the best solution is found. For
example: Finding the best path for the travelling salesman problem. Here best path
means that travelling all the cities and the cost of travelling should be minimum.
o Satisficing: It stops finding the solution as soon as the satisfactory solution is
found. Or example, finding the travelling salesman path which is within 10% of
optimal.
o Often Brute force algorithms require exponential time. Various heuristics and
optimization can be used:
o Heuristic: A rule of thumb that helps you to decide which possibilities we should
look at first.
o Optimization: A certain possibilities are eliminated without exploring all of them.

Let's understand the brute force search through an example.

Suppose we have converted the problem in the form of the tree shown as below:
Brute force search considers each and every state of a tree, and the state is represented
in the form of a node. As far as the starting position is concerned, we have two choices,
i.e., A state and B state. We can either generate state A or state B. In the case of B state, we
have two states, i.e., state E and F.

In the case of brute force search, each state is considered one by one. As we can observe
in the above tree that the brute force search takes 12 steps to find the solution.

On the other hand, backtracking, which uses Depth-First search, considers the below
states only when the state provides a feasible solution. Consider the above tree, start from
the root node, then move to node A and then node C. If node C does not provide the
feasible solution, then there is no point in considering the states G and H. We backtrack
from node C to node A. Then, we move from node A to node D. Since node D does not
provide the feasible solution, we discard this state and backtrack from node D to node A.

We move to node B, then we move from node B to node E. We move from node E to node
K; Since k is a solution, so it takes 10 steps to find the solution. In this way, we eliminate
a greater number of states in a single iteration. Therefore, we can say that backtracking
is faster and more efficient than the brute force approach.

Advantages of a brute-force algorithm

The following are the advantages of the brute-force algorithm:

o This algorithm finds all the possible solutions, and it also guarantees that it finds the
correct solution to a problem.
o This type of algorithm is applicable to a wide range of domains.
o It is mainly used for solving simpler and small problems.
o It can be considered a comparison benchmark to solve a simple problem and does not
require any particular domain knowledge.
Disadvantages of a brute-force algorithm
The following are the disadvantages of the brute-force algorithm:

o It is an inefficient algorithm as it requires solving each and every state.

o It is a very slow algorithm to find the correct solution as it solves each state without
considering whether the solution is feasible or not.
o The brute force algorithm is neither constructive nor creative as compared to other
algorithms.

Greedy Algorithm
The greedy method is one of the strategies like Divide and conquer used to solve the
problems. This method is used for solving optimization problems. An optimization
problem is a problem that demands either maximum or minimum results. Let's
understand through some terms.

The Greedy method is the simplest and straightforward approach. It is not an algorithm,
but it is a technique. The main function of this approach is that the decision is taken
on the basis of the currently available information. Whatever the current
information is present, the decision is made without worrying about the effect of
the current decision in future.

This technique is basically used to determine the feasible solution that may or may not
be optimal. The feasible solution is a subset that satisfies the given criteria. The optimal
solution is the solution which is the best and the most favourable solution in the subset.
In the case of feasible, if more than one solution satisfies the given criteria then those
solutions will be considered as the feasible, whereas the optimal solution is the best
solution among all the solutions.

Characteristics of Greedy method

The following are the characteristics of a greedy method:

o To construct the solution in an optimal way, this algorithm creates two sets where one
set contains all the chosen items, and another set contains the rejected items.
o A Greedy algorithm makes good local choices in the hope that the solution should be
either feasible or optimal.

Components of Greedy Algorithm

The components that can be used in the greedy algorithm are:
 o Candidate set: A solution that is created from the set is known as a candidate set.
o Selection function: This function is used to choose the candidate or subset which can be
added in the solution.
o Feasibility function: A function that is used to determine whether the candidate or
subset can be used to contribute to the solution or not.
o Objective function: A function is used to assign the value to the solution or the partial
solution.
o Solution function: This function is used to intimate whether the complete function has
been reached or not.

Applications of Greedy Algorithm

o It is used in finding the shortest path.

o It is used to find the minimum spanning tree using the prim's algorithm or the Kruskal's
algorithm.
o It is used in a job sequencing with a deadline.
o This algorithm is also used to solve the fractional knapsack problem.

Pseudo code of Greedy Algorithm

1. Algorithm Greedy (a, n)
2. {
3. Solution : = 0;
4. for i = 0 to n do
5. {
6. x: = select(a);
7. if feasible(solution, x)
8. {
9. Solution: = union(solution , x)
10. }
11. return solution;
12. } }

The above is the greedy algorithm. Initially, the solution is assigned with zero value. We
pass the array and number of elements in the greedy algorithm. Inside the for loop, we
select the element one by one and checks whether the solution is feasible or not. If the
solution is feasible, then we perform the union.

Let's understand through an example.

Suppose there is a problem 'P'. I want to travel from A to B shown as below:

P:A→B

The problem is that we have to travel this journey from A to B. There are various
solutions to go from A to B. We can go from A to B by walk, car, bike, train, aeroplane,
etc. There is a constraint in the journey that we have to travel this journey within 12
hrs. If I go by train or aeroplane then only, I can cover this distance within 12 hrs. There
are many solutions to this problem but there are only two solutions that satisfy the
constraint.

If we say that we have to cover the journey at the minimum cost. This means that we have
to travel this distance as minimum as possible, so this problem is known as a
minimization problem. Till now, we have two feasible solutions, i.e., one by train and
another one by air. Since travelling by train will lead to the minimum cost so it is an
optimal solution. An optimal solution is also the feasible solution, but providing the
best result so that solution is the optimal solution with the minimum cost. There would
be only one optimal solution.

The problem that requires either minimum or maximum result then that problem is
known as an optimization problem. Greedy method is one of the strategies used for
solving the optimization problems.

Disadvantages of using Greedy algorithm

Greedy algorithm makes decisions based on the information available at each phase
without considering the broader problem. So, there might be a possibility that the greedy
solution does not give the best solution for every problem.

It follows the local optimum choice at each stage with a intend of finding the global
optimum. Let's understand through an example.
Consider the graph which is given below:

We have to travel from the source to the destination at the minimum cost. Since we have
three feasible solutions having cost paths as 10, 20, and 5. 5 is the minimum cost path so
it is the optimal solution. This is the local optimum, and in this way, we find the local
optimum at each stage in order to calculate the global optimal solution.

Branch and bound vs backtracking

Before understanding the branch and bound and backtracking differences, we should
know about the branch and bound and backtracking separately.

What is Backtracking?

Backtracking is nothing but the modified process of the Brute force approach. It is a
technique where multiple solutions to a problem are available, and it searches for the
solution to the problem among all the available options. Let's consider the example of
brute force search as backtracking follows the brute force search approach.

Consider the box, and we have three objects of three different colors. One object is of red
color, the second object is of green color, and the third object is of blue color. Now, we
have to keep these objects inside the box, and we have multiple options. As per the Brute
force approach, we have to consider all the options and identify the best option among all
the possible options.

Let's consider all the possible solutions to this problem.

Suppose we first fill red object, after then green object and then blue object. This is the
first solution to this problem. The possible solution is red, green, and blue.
The second solution is to keep the red object, then the blue object, and then the green
object. The possible solution red, blue, and green.

The third solution can be to keep the green object, then the red object and then the blue
object. The possible solution is green, red and blue.

The fourth solution is to keep the green object, then the blue object and then the red
object. The possible solution is green, blue and red.

The fifth solution is to keep the blue object, then green object and then red object. The
possible solution is blue, green and red.

The sixth solution is to keep the blue object, then the red object and then the green object.
The possible solution is blue, red and green.
The above are the possible solutions, and we have to identify the best possible solution
out of all the possible solutions. This approach is known as a brute force approach.
Backtracking is similar to the brute force approach, but it is a modified process of the
brute force approach.

Let's see how backtracking is different from the brute force approach.

The above is the figure that shows the possible solutions to the above problem. Now we
will see that how these solutions are represented in backtracking.

In backtracking, solutions are represented in the form of a tree and that tree is known as
a state space tree. Since backtracking follows the DFS, the tree will be formed using DFS,
which is known as a State Space tree.

Let's create the tree.

Consider the first solution, i.e., red, green, blue, and it can be represented in the form of
a tree as shown as below.

Let's create the tree.

Consider the first solution, i.e., red, green, blue, and it can be represented in the form of
a tree as shown as below.
Consider the second solution, i.e., red, blue, green. Since there is no more object after
blue so we will backtrack and move to the green. Instead of taking green, we first take
blue and then green, shown as below:

The next solution is green, red and blue. Since we cannot explore the green object, so
we move back and reach the blue object. We cannot explore the blue object, so we again
move back and reach to the red object. Instead of using the red object, we will use the
green object. After the green object, we use the red object and then we use the blue
object. We cannot explore the blue object further. Now the sequence green, red and blue
is formed as shown as below:
The next solution is green, blue and red. Since we cannot explore the blue object, we
move back and reach the red object. Instead of using a red color object, we will use the
blue color object and then we use the red color object. Now the sequence green, blue and
red is formed.

The next solution is blue, green and red. Since we cannot explore the red object, so we
backtrack and reach the blue object. We cannot explore the blue object so we backtrack
and reach the green object. Instead of using the green object, we will use the blue color
object then we use the green object and then we use the red color object. The sequence,
i.e., blue, green and red, is formed as shown as below:

The next solution is blue, red and green. Since we cannot explore red object so we
backtrack and reach to the green object. Instead of using the green object, we use the red
object and then we use the green object.

The above is the state space tree that shows all the possible solutions related to the
problem. Therefore, we can say that the state space tree can be used to represent all the
solutions in backtracking. Using backtracking, we can solve the problem that has some
constraints and we can find the solution based on these constraints. Suppose in the
above example; the constraint is blue color object must not be in the middle (bounding
function).

The first solution is red, green and blue. Since blue color object is not in the middle so
we do need to perform any modification.

The second solution is red, blue, and green. Since blue color is in the middle so we will
remove the green color as shown as below:

The next solution is green, red, and blue. Since blue color object is not in the middle so
we do need to perform any modification.

The next solution is green, blue and red. Since blue color is in the middle so we will
remove the red color as shown as below:
The above is the state space tree that does not have blue object in the middle of the
solution.

Branch and Bound

It is similar to backtracking. The concept branch and bound and backtracking follow the
Brute force method and generate the state space tree. But both of them follows different
approaches. The way to generate the tree is different.

Backtracking follows the DFS, whereas the branch n bound follows the BFS to generate
the tree. Now we will understand the branch n bound through an example. As it follows
the BFS, so first all the nodes of the same level are added then we move to the next level.

Consider the same example that we discussed in the backtracking.

First, we take the root node.

Now we have three possibilities that either we select red, green, or blue objects as shown
below. In this case, we have completed the first level.
Now we move to the next level.

In the case of red object, we have two possibilities that either we select green or blue
object shown as below:

In the case of green object, we have two possibilities that either we select red or blue
object shown as below:

In the case of blue object, we have two possibilities that either we select red or green
object shown as below:
We move to the third level.

In the case of a green object, only one object, i.e., blue, can be added.

In the case of a blue object, only one object, i.e., green, can be added.
In the case of a red object, only one object, i.e., blue, can be added.

In the case of a blue object, only one object, i.e., red, can be added.
In the case of a green object, only one object, i.e., red, can be added.

In the case of a red object, only one object, i.e., green, can be added.
Examples:

The problems that can be solved by using backtracking are:

o 8 Queens problem
o Knapsack problem using backtracking

The problem that can be solved by using branch and bound is:

o Travelling Salesman Problem

Differences between Branch n bound and Backtracking

Backtracking Branch and bound

Backtracking is a problem-solving technique so Branch n bound is a problem-solving

it solves the decision problem. technique so it solves the
optimization problem.

When we find the solution using backtracking When we find the solution using
then some bad choices can be made. Branch n bound then it provides a
better solution so there are no
chances of making a bad choice.

Backtracking uses a Depth first search. It is not necessary that branch n

bound uses Depth first search. It can
even use a Breadth-first search and
best-first search.

The state space tree is searched until the The state space tree needs to be
solution of the problem is obtained. searched completely as the optimum
solution can be present anywhere in
the state space tree.

In backtracking, all the possible solutions are In branch and bound, based on
tried. If the solution does not satisfy the search; bounding values are
constraint, then we backtrack and look for calculated. According to the bounding
another solution. values, we either stop there or extend.

Applications of backtracking are n-Queens Applications of branch and bound are

problem, Sum of subset. knapsack problem, travelling
salesman problem, etc.

Backtracking is more efficient than the Branch Branch n bound is less efficient.
and bound.

It contains the feasibility function. It contains the bounding function.

Backtracking solves the given problem by first Branch and bound solves the given
finding the solution of the subproblem and then problem by dividing the problem into
recursively solves the other problems based on two atleast subproblems.
the solution of the first subproblem.
Bin Packing Problem (Minimize
number of used Bins)
iven n items of different weights and bins each of capacity c, assign each
item to a bin such that number of total used bins is minimized. It may be
assumed that all items have weights smaller than bin capacity.
Example:
Input: weight[] = {4, 8, 1, 4, 2, 1}
Bin Capacity c = 10
Output: 2
We need minimum 2 bins to accommodate all items
First bin contains {4, 4, 2} and second bin {8, 1, 1}

Input: weight[] = {9, 8, 2, 2, 5, 4}

Bin Capacity c = 10
Output: 4
We need minimum 4 bins to accommodate all items.

Input: weight[] = {2, 5, 4, 7, 1, 3, 8};

Bin Capacity c = 10
Output: 3
Lower Bound
We can always find a lower bound on minimum number of bins required.
The lower bound can be given as :
Min no. of bins >= Ceil ((Total Weight) / (Bin Capacity))
In the above examples, lower bound for first example is “ceil(4 + 8 + 1 + 4 +
2 + 1)/10” = 2 and lower bound in second example is “ceil(9 + 8 + 2 + 2 + 5
+ 4)/10” = 3.
This problem is a NP Hard problem and finding an exact minimum number
of bins takes exponential time. Following are approximate algorithms for this
problem.
Applications
1. Loading of containers like trucks.
2. Placing data on multiple disks.
3. Job scheduling.
4. Packing advertisements in fixed length radio/TV station breaks.
5. Storing a large collection of music onto tapes/CD’s, etc.
Online Algorithms
These algorithms are for Bin Packing problems where items arrive one at a
time (in unknown order), each must be put in a bin, before considering the
next item.
1. Next Fit:
When processing next item, check if it fits in the same bin as the last item.
Use a new bin only if it does not.
Below is C++ implementation for this algorithm.
# Python3 implementation for above approach

def nextfit(weight, c):

res = 0

rem = c

for _ in range(len(weight)):

if rem >= weight[_]:

rem = rem - weight[_]

else:

res += 1

rem = c - weight[_]

return res

# Driver Code

weight = [2, 5, 4, 7, 1, 3, 8]

c = 10

print("Number of bins required in Next Fit :",

nextfit(weight, c))

# This code is contributed by code_freak

Output:
Number of bins required in Next Fit : 4
Next Fit is a simple algorithm. It requires only O(n) time and O(1) extra
space to process n items.
Next Fit is 2 approximate, i.e., the number of bins used by this algorithm is
bounded by twice of optimal. Consider any two adjacent bins. The sum of
items in these two bins must be > c; otherwise, NextFit would have put all
 the items of second bin into the first. The same holds for all other bins.
Thus, at most half the space is wasted, and so Next Fit uses at most 2M
bins if M is optimal.
2. First Fit:
When processing the next item, scan the previous bins in order and place
the item in the first bin that fits. Start a new bin only if it does not fit in any of
the existing bins.
• C++
• Java
• Python3
• C#
• Javascript

# Python program to find number of bins required using

# First Fit algorithm.

# Returns number of bins required using first fit

# online algorithm

def firstFit(weight, n, c):

# Initialize result (Count of bins)

res = 0

# Create an array to store remaining space in bins

# there can be at most n bins

bin_rem = [0]*n
 # Place items one by one

for i in range(n):

# Find the first bin that can accommodate

# weight[i]

j =0

while( j < res):

if (bin_rem[j] >= weight[i]):

bin_rem[j] = bin_rem[j] - weight[i]

break

j+=1

# If no bin could accommodate weight[i]

if (j == res):

bin_rem[res] = c - weight[i]

res= res+1

return res

# Driver program

weight = [2, 5, 4, 7, 1, 3, 8]

c = 10

n = len(weight)
 print("Number of bins required in First Fit : ",firstFit(weight, n, c))

# This code is contributed by shubhamsingh10

Output:
Number of bins required in First Fit : 4
The above implementation of First Fit requires O(n 2) time, but First Fit can
be implemented in O(n Log n) time using Self-Balancing Binary Search
Trees.
If M is the optimal number of bins, then First Fit never uses more than 1.7M
bins. So First-Fit is better than Next Fit in terms of upper bound on number
of bins.
3. Best Fit:
The idea is to places the next item in the *tightest* spot. That is, put it in the
bin so that the smallest empty space is left.
• C++
• Java
• Python3
• C#
• Javascript

# Python3 program to find number

# of bins required using

# First Fit algorithm.

# Returns number of bins required

# using first fit

# online algorithm

def firstFit(weight, n, c):

# Initialize result (Count of bins)

res = 0;

# Create an array to store

# remaining space in bins

# there can be at most n bins

bin_rem = [0]*n;

# Place items one by one

for i in range(n):

# Find the first bin that

# can accommodate

# weight[i]

j = 0;

# Initialize minimum space

# left and index

# of best bin

min = c + 1;
 bi = 0;

for j in range(res):

if (bin_rem[j] >= weight[i] and bin_rem[j] -

weight[i] < min):

bi = j;

min = bin_rem[j] - weight[i];

# If no bin could accommodate weight[i],

# create a new bin

if (min == c + 1):

bin_rem[res] = c - weight[i];

res += 1;

else: # Assign the item to best bin

bin_rem[bi] -= weight[i];

return res;

# Driver code

if __name__ == '__main__':

weight = [ 2, 5, 4, 7, 1, 3, 8 ];

c = 10;

n = len(weight);
 print("Number of bins required in First Fit : ",

firstFit(weight, n, c));

# This code is contributed by Rajput-Ji

Output:
Number of bins required in Best Fit : 4
Best Fit can also be implemented in O(n Log n) time using Self-Balancing
Binary Search Trees.
If M is the optimal number of bins, then Best Fit never uses more than 1.7M
bins. So Best Fit is same as First Fit and better than Next Fit in terms of
upper bound on number of bins.
4. Worst Fit:
The idea is to places the next item in the least tight spot to even out the
bins. That is, put it in the bin so that most empty space is left.
• C++
• Java
• Python3
• C#
• Javascript

# Python program to find number of bins required using# Worst fit algorithm.# Returns
number of bins required using worst fit# online algorithm

def worstFit( weight, n, c):

# Initialize result (Count of bins)

res = 0
# Create an array to store remaining space in bins

# there can be at most n bins

bin_rem = [0 for i in range(n)]

# Place items one by one

for i in range(n):

# Find the best bin that can accommodate

# weight[i]

# Initialize maximum space left and index

# of worst bin

mx,wi = -1,0

for j in range(res):

if (bin_rem[j] >= weight[i] and bin_rem[j] - weight[i] > mx):

wi = j

mx = bin_rem[j] - weight[i]

# If no bin could accommodate weight[i],

 # create a new bin

if (mx == -1):

bin_rem[res] = c - weight[i]

res += 1

else: # Assign the item to best bin

bin_rem[wi] -= weight[i]

return res

# Driver program

weight = [ 2, 5, 4, 7, 1, 3, 8 ]

c = 10

n = len(weight)

print(f"Number of bins required in Worst Fit : {worstFit(weight, n, c)}")

# This code is contributed by shinjanpatra

Output:
Number of bins required in Worst Fit : 4
Worst Fit can also be implemented in O(n Log n) time using Self-Balancing
Binary Search Trees.
If M is the optimal number of bins, then Best Fit never uses more than 2M-2
bins. So Worst Fit is same as Next Fit in terms of upper bound on number of
bins.

Offline Algorithms
 In the offline version, we have all items upfront. Unfortunately offline version
is also NP Complete, but we have a better approximate algorithm for it. First
Fit Decreasing uses at most (4M + 1)/3 bins if the optimal is M.
4. First Fit Decreasing:
A trouble with online algorithms is that packing large items is difficult,
especially if they occur late in the sequence. We can circumvent this by
*sorting* the input sequence, and placing the large items first. With sorting,
we get First Fit Decreasing and Best Fit Decreasing, as offline analogues of
online First Fit and Best Fit.
• C++
• Java
• Python3
• C#
• Javascript

# Python program to find number of bins required using

# First Fit Decreasing algorithm.

# Returns number of bins required using first fit

# online algorithm

def firstFit(weight, n, c):

# Initialize result (Count of bins)

res = 0

# Create an array to store remaining space in bins

# there can be at most n bins

bin_rem = [0]*n
 # Place items one by one

for i in range(n):

# Find the first bin that can accommodate

# weight[i]

j =0

while( j < res):

if (bin_rem[j] >= weight[i]):

bin_rem[j] = bin_rem[j] - weight[i]

break

j+=1

# If no bin could accommodate weight[i]

if (j == res):

bin_rem[res] = c - weight[i]

res= res+1

return res

# Returns number of bins required using first fit

# decreasing offline algorithm

 def firstFitDec(weight, n, c):

# First sort all weights in decreasing order

[Link](reverse = True)

# Now call first fit for sorted items

return firstFit(weight, n, c)

# Driver program

weight = [ 2, 5, 4, 7, 1, 3, 8 ]

c = 10

n = len(weight)

print("Number of bins required in First Fit Decreasing : ",str(firstFitDec(weight, n,

# This code is contributed by shinjanpatra

Output:
Number of bins required in First Fit Decreasing : 3
First Fit decreasing produces the best result for the sample input because
items are sorted first.
First Fit Decreasing can also be implemented in O(n Log n) time using Self-
Balancing Binary Search Trees.

Knapsack problem
Here knapsack is like a container or a bag. Suppose we have given some items which
have some weights or profits. We have to put some items in the knapsack in such a
way total value produces a maximum profit.
For example, the weight of the container is 20 kg. We have to select the items in such
a way that the sum of the weight of items should be either smaller than or equal to
the weight of the container, and the profit should be maximum.

There are two types of knapsack problems:

o 0/1 knapsack problem

o Fractional knapsack problem

We will discuss both the problems one by one. First, we will learn about the 0/1
knapsack problem.

Play Video

What is the 0/1 knapsack problem?

The 0/1 knapsack problem means that the items are either completely or no items
are filled in a knapsack. For example, we have two items having weights 2kg and
3kg, respectively. If we pick the 2kg item then we cannot pick 1kg item from the 2kg
item (item is not divisible); we have to pick the 2kg item completely. This is a 0/1
knapsack problem in which either we pick the item completely or we will pick that
item. The 0/1 knapsack problem is solved by the dynamic programming.

What is the fractional knapsack problem?

The fractional knapsack problem means that we can divide the item. For example,
we have an item of 3 kg then we can pick the item of 2 kg and leave the item of 1 kg.
The fractional knapsack problem is solved by the Greedy approach.

Example of 0/1 knapsack problem.

Consider the problem having weights and profits are:

Weights: {3, 4, 6, 5}

Profits: {2, 3, 1, 4}

The weight of the knapsack is 8 kg

The number of items is 4

The above problem can be solved by using the following method:

xi = {1, 0, 0, 1}

= {0, 0, 0, 1}
= {0, 1, 0, 1}

The above are the possible combinations. 1 denotes that the item is completely
picked and 0 means that no item is picked. Since there are 4 items so possible
combinations will be:

24 = 16; So. There are 16 possible combinations that can be made by using the above
problem. Once all the combinations are made, we have to select the combination
that provides the maximum profit.

Another approach to solve the problem is dynamic programming approach. In

dynamic programming approach, the complicated problem is divided into sub-
problems, then we find the solution of a sub-problem and the solution of the sub-
problem will be used to find the solution of a complex problem.

How this problem can be solved by using the Dynamic

programming approach?
First,

we create a matrix shown as below:

0 1 2 3 4 5 6 7 8

In the above matrix, columns represent the weight, i.e., 8. The rows represent the
profits and weights of items. Here we have not taken the weight 8 directly, problem
is divided into sub-problems, i.e., 0, 1, 2, 3, 4, 5, 6, 7, 8. The solution of the sub-
problems would be saved in the cells and answer to the problem would be stored in
the final cell. First, we write the weights in the ascending order and profits according
to their weights shown as below:

wi = {3, 4, 5, 6}
pi = {2, 3, 4, 1}

The first row and the first column would be 0 as there is no item for w=0

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0

2 0

3 0

4 0

When i=1, W=1

w1 = 3; Since we have only one item in the set having weight 3, but the capacity of
the knapsack is 1. We cannot fill the item of 3kg in the knapsack of capacity 1 kg so
add 0 at M[1][1] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0

2 0

3 0

4 0

When i = 1, W = 2

w1 = 3; Since we have only one item in the set having weight 3, but the capacity of
the knapsack is 2. We cannot fill the item of 3kg in the knapsack of capacity 2 kg so
add 0 at M[1][2] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0

2 0

3 0

4 0

When i=1, W=3

w1 = 3; Since we have only one item in the set having weight equal to 3, and weight
of the knapsack is also 3; therefore, we can fill the knapsack with an item of weight
equal to 3. We put profit corresponding to the weight 3, i.e., 2 at M[1][3] shown as
below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2

2 0

3 0

4 0

When i=1, W = 4

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight
of the knapsack is 4; therefore, we can fill the knapsack with an item of weight equal
to 3. We put profit corresponding to the weight 3, i.e., 2 at M[1][4] shown as below:

0 1 2 3 4 5 6 7 8
 0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2

2 0

3 0

4 0

When i=1, W = 5

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight
of the knapsack is 5; therefore, we can fill the knapsack with an item of weight equal
to 3. We put profit corresponding to the weight 3, i.e., 2 at M[1][5] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2

2 0

3 0

4 0

When i =1, W=6

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight
of the knapsack is 6; therefore, we can fill the knapsack with an item of weight equal
to 3. We put profit corresponding to the weight 3, i.e., 2 at M[1][6] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2
 2 0

3 0

4 0

When i=1, W = 7

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight
of the knapsack is 7; therefore, we can fill the knapsack with an item of weight equal
to 3. We put profit corresponding to the weight 3, i.e., 2 at M[1][7] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2

2 0

3 0

4 0

When i =1, W =8

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight
of the knapsack is 8; therefore, we can fill the knapsack with an item of weight equal
to 3. We put profit corresponding to the weight 3, i.e., 2 at M[1][8] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0

3 0
 4 0

Now the value of 'i' gets incremented, and becomes 2.

When i =2, W = 1

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have only one
item in the set having weight equal to 4, and the weight of the knapsack is 1. We
cannot put the item of weight 4 in a knapsack, so we add 0 at M[2][1] shown as
below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0

3 0

4 0

When i =2, W = 2

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have only one
item in the set having weight equal to 4, and the weight of the knapsack is 2. We
cannot put the item of weight 4 in a knapsack, so we add 0 at M[2][2] shown as
below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0

3 0
 4 0

When i =2, W = 3

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in
the set having weights 3 and 4, and the weight of the knapsack is 3. We can put the
item of weight 3 in a knapsack, so we add 2 at M[2][3] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2

3 0

4 0

When i =2, W = 4

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in
the set having weights 3 and 4, and the weight of the knapsack is 4. We can put item
of weight 4 in a knapsack as the profit corresponding to weight 4 is more than the
item having weight 3, so we add 3 at M[2][4] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3

3 0

4 0
When i = 2, W = 5

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in
the set having weights 3 and 4, and the weight of the knapsack is 5. We can put item
of weight 4 in a knapsack and the profit corresponding to weight is 3, so we add 3
at M[2][5] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3

3 0

4 0

When i = 2, W = 6

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in
the set having weights 3 and 4, and the weight of the knapsack is 6. We can put item
of weight 4 in a knapsack and the profit corresponding to weight is 3, so we add 3
at M[2][6] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3

3 0

4 0

When i = 2, W = 7
The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in
the set having weights 3 and 4, and the weight of the knapsack is 7. We can put item
of weight 4 and 3 in a knapsack and the profits corresponding to weights are 2 and
3; therefore, the total profit is 5, so we add 5 at M[2][7] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 0 3 3 3 5

3 0

4 0

When i = 2, W = 8

The weight corresponding to the value 2 is 4, i.e., w2 = 4. Since we have two items in
the set having weights 3 and 4, and the weight of the knapsack is 7. We can put item
of weight 4 and 3 in a knapsack and the profits corresponding to weights are 2 and
3; therefore, the total profit is 5, so we add 5 at M[2][7] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0

4 0

Now the value of 'i' gets incremented, and becomes 3.

When i = 3, W = 1
The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items
in the set having weights 3, 4, and 5, and the weight of the knapsack is 1. We cannot
put neither of the items in a knapsack, so we add 0 at M[3][1] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0

4 0

When i = 3, W = 2

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items
in the set having weight 3, 4, and 5, and the weight of the knapsack is 1. We cannot
put neither of the items in a knapsack, so we add 0 at M[3][2] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0

4 0

When i = 3, W = 3

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items
in the set of weight 3, 4, and 5 respectively and weight of the knapsack is 3. The item
with a weight 3 can be put in the knapsack and the profit corresponding to the item
is 2, so we add 2 at M[3][3] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2

4 0

When i = 3, W = 4

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items
in the set of weight 3, 4, and 5 respectively, and weight of the knapsack is 4. We can
keep the item of either weight 3 or 4; the profit (3) corresponding to the weight 4 is
more than the profit corresponding to the weight 3 so we add 3 at M[3][4] shown
as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3

4 0

When i = 3, W = 5

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items
in the set of weight 3, 4, and 5 respectively, and weight of the knapsack is 5. We can
keep the item of either weight 3, 4 or 5; the profit (3) corresponding to the weight
4 is more than the profits corresponding to the weight 3 and 5 so we add 3 at
M[3][5] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3

4 0

When i =3, W = 6

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items
in the set of weight 3, 4, and 5 respectively, and weight of the knapsack is 6. We can
keep the item of either weight 3, 4 or 5; the profit (3) corresponding to the weight
4 is more than the profits corresponding to the weight 3 and 5 so we add 3 at
M[3][6] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3

4 0

When i =3, W = 7

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items
in the set of weight 3, 4, and 5 respectively, and weight of the knapsack is 7. In this
case, we can keep both the items of weight 3 and 4, the sum of the profit would be
equal to (2 + 3), i.e., 5, so we add 5 at M[3][7] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5

4 0

When i = 3, W = 8

The weight corresponding to the value 3 is 5, i.e., w3 = 5. Since we have three items
in the set of weight 3, 4, and 5 respectively, and the weight of the knapsack is 8. In
this case, we can keep both the items of weight 3 and 4, the sum of the profit would
be equal to (2 + 3), i.e., 5, so we add 5 at M[3][8] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0

Now the value of 'i' gets incremented and becomes 4.

When i = 4, W = 1

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items
in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 1.
The weight of all the items is more than the weight of the knapsack, so we cannot
add any item in the knapsack; Therefore, we add 0 at M[4][1] shown as below:
 0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0

When i = 4, W = 2

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items
in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 2.
The weight of all the items is more than the weight of the knapsack, so we cannot
add any item in the knapsack; Therefore, we add 0 at M[4][2] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0

When i = 4, W = 3

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items
in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 3.
The item with a weight 3 can be put in the knapsack and the profit corresponding
to the weight 4 is 2, so we will add 2 at M[4][3] shown as below:

0 1 2 3 4 5 6 7 8
 0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0 2

When i = 4, W = 4

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items
in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 4.
The item with a weight 4 can be put in the knapsack and the profit corresponding
to the weight 4 is 3, so we will add 3 at M[4][4] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0 2 3

When i = 4, W = 5

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items
in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 5.
The item with a weight 4 can be put in the knapsack and the profit corresponding
to the weight 4 is 3, so we will add 3 at M[4][5] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0
 1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0 2 3 3

When i = 4, W = 6

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items
in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 6.
In this case, we can put the items in the knapsack either of weight 3, 4, 5 or 6 but the
profit, i.e., 4 corresponding to the weight 6 is highest among all the items; therefore,
we add 4 at M[4][6] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 1 3 3 3 5 5

4 0 0 0 2 3 3 4

When i = 4, W = 7

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items
in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 7.
Here, if we add two items of weights 3 and 4 then it will produce the maximum
profit, i.e., (2 + 3) equals to 5, so we add 5 at M[4][7] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0
 1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5

When i = 4, W = 8

The weight corresponding to the value 4 is 6, i.e., w4 = 6. Since we have four items
in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 8.
Here, if we add two items of weights 3 and 4 then it will produce the maximum
profit, i.e., (2 + 3) equals to 5, so we add 5 at M[4][8] shown as below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5 5

As we can observe in the above table that 5 is the maximum profit among all the
entries. The pointer points to the last row and the last column having 5 value. Now
we will compare 5 value with the previous row; if the previous row, i.e., i = 3
contains the same value 5 then the pointer will shift upwards. Since the previous
row contains the value 5 so the pointer will be shifted upwards as shown in the
below table:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2
 2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5 5

Again, we will compare the value 5 from the above row, i.e., i = 2. Since the above
row contains the value 5 so the pointer will again be shifted upwards as shown in
the below table:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2

2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5 5

Again, we will compare the value 5 from the above row, i.e., i = 1. Since the above
row does not contain the same value so we will consider the row i=1, and the weight
corresponding to the row is 4. Therefore, we have selected the weight 4 and we have
rejected the weights 5 and 6 shown below:

x = { 1, 0, 0}

The profit corresponding to the weight is 3. Therefore, the remaining profit is (5 -

3) equals to 2. Now we will compare this value 2 with the row i = 2. Since the row (i
= 1) contains the value 2; therefore, the pointer shifted upwards shown below:

0 1 2 3 4 5 6 7 8

0 0 0 0 0 0 0 0 0 0

1 0 0 0 2 2 2 2 2 2
 2 0 0 0 2 3 3 3 5 5

3 0 0 0 2 3 3 3 5 5

4 0 0 0 2 3 3 4 5 5

Again we compare the value 2 with a above row, i.e., i = 1. Since the row i =0 does
not contain the value 2, so row i = 1 will be selected and the weight corresponding
to the i = 1 is 3 shown below:

X = {1, 1, 0, 0}

The profit corresponding to the weight is 2. Therefore, the remaining profit is 0. We

compare 0 value with the above row. Since the above row contains a 0 value but the
profit corresponding to this row is 0. In this problem, two weights are selected, i.e.,
3 and 4 to maximize the profit.

Travelling Salesman Problem using

Dynamic Programming
Travelling Salesman Problem (TSP):
Given a set of cities and the distance between every pair of cities, the
problem is to find the shortest possible route that visits every city exactly
once and returns to the starting point. Note the difference
between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem is to
find if there exists a tour that visits every city exactly once. Here we know
that Hamiltonian Tour exists (because the graph is complete) and in fact,
many such tours exist, the problem is to find a minimum weight Hamiltonian
Cycle.
For example, consider the graph shown in the figure on the right side. A
TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15
which is 80. The problem is a famous NP-hard problem. There is no
polynomial-time know solution for this problem. The following are different
solutions for the traveling salesman problem.
Naive Solution:
1) Consider city 1 as the starting and ending point.
2) Generate all (n-1)! Permutations of cities.
3) Calculate the cost of every permutation and keep track of the minimum
cost permutation.
4) Return the permutation with minimum cost.
Time Complexity: Θ(n!)
Dynamic Programming:
Let the given set of vertices be {1, 2, 3, 4,….n}. Let us consider 1 as starting
and ending point of output. For every other vertex I (other than 1), we find
the minimum cost path with 1 as the starting point, I as the ending point, and
all vertices appearing exactly once. Let the cost of this path cost (i), and the
cost of the corresponding Cycle would cost (i) + dist(i, 1) where dist(i, 1) is
the distance from I to 1. Finally, we return the minimum of all [cost(i) + dist(i,
1)] values. This looks simple so far.
 Now the question is how to get cost(i)? To calculate the cost(i) using
Dynamic Programming, we need to have some recursive relation in terms of
sub-problems.
Let us define a term C(S, i) be the cost of the minimum cost path visiting
each vertex in set S exactly once, starting at 1 and ending at i. We start with
all subsets of size 2 and calculate C(S, i) for all subsets where S is the
subset, then we calculate C(S, i) for all subsets S of size 3 and so on. Note
that 1 must be present in every subset.
If size of S is 2, then S must be {1, i},
C(S, i) = dist(1, i)
Else if size of S is greater than 2.
C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j
!= i and j != 1.
Below is the dynamic programming solution for the problem using top down
recursive+memoized approach:-
For maintaining the subsets we can use the bitmasks to represent the
remaining nodes in our subset. Since bits are faster to operate and there
are only few nodes in graph, bitmasks is better to use.
For example: –
10100 represents node 2 and node 4 are left in set to be processed
010010 represents node 1 and 4 are left in subset.
NOTE:- ignore the 0th bit since our graph is 1-based
• C++
• Java
• Python3
• C#
• Javascript

n = 4 # there are four nodes in example graph (graph is 1-

based)

# dist[i][j] represents shortest distance to go from i to j

# this matrix can be calculated for any given graph using

# all-pair shortest path algorithms

dist = [[0, 0, 0, 0, 0], [0, 0, 10, 15, 20], [

0, 10, 0, 25, 25], [0, 15, 25, 0, 30], [0, 20, 25, 30,
0]]

# memoization for top down recursion

memo = [[-1]*(1 << (n+1)) for _ in range(n+1)]

def fun(i, mask):

# base case

# if only ith bit and 1st bit is set in our mask,

# it implies we have visited all other nodes already

if mask == ((1 << i) | 3):

return dist[1][i]

# memoization

if memo[i][mask] != -1:

return memo[i][mask]

res = 10**9 # result of this sub-problem

 # we have to travel all nodes j in mask and end the path
at ith node

# so for every node j in mask, recursively calculate

cost of

# travelling all nodes in mask

# except i and then travel back from node j to node i

taking

# the shortest path take the minimum of all possible j

nodes

for j in range(1, n+1):

if (mask & (1 << j)) != 0 and j != i and j != 1:

res = min(res, fun(j, mask & (~(1 << i))) +

dist[j][i])

memo[i][mask] = res # storing the minimum value

return res

# Driver program to test above logic

ans = 10**9

for i in range(1, n+1):

# try to go from node 1 visiting all nodes in between to

i

# then return from i taking the shortest route to 1

ans = min(ans, fun(i, (1 << (n+1))-1) + dist[i][1])

 print("The cost of most efficient tour = " + str(ans))

# This code is contributed by Serjeel Ranjan

Output
The cost of most efficient tour = 80
Time Complexity : O(n2*2n)
Auxiliary Space : O(n2) , where n is number of Nodes/Cities here.
For a set of size n, we consider n-2 subsets each of size n-1 such that all
subsets don’t have nth in them. Using the above recurrence relation, we can
write a dynamic programming-based solution. There are at most O(n*2n)
subproblems, and each one takes linear time to solve. The total running
time is therefore O(n2*2n). The time complexity is much less than O(n!) but
still exponential. The space required is also exponential. So this approach is
also infeasible even for a slightly higher number of vertices.