K.CHAITANYA DEEPTHI ASST.

PROF CSE,DEPT

UNIT – IV: Backtracking: General Method, 8-Queens Problem, Sum of Subsets problem,
Graph Coloring, 0/1 Knapsack Problem.

Branch and Bound: The General Method, 0/1 Knapsack Problem, Travelling Salesperson
problem.

Backtracking: General Method

Backtracking: Backtracking is an algorithm that finds all the possible solutions and selects
the desired solution from the given set of solutions.

 Backtracking is one of the techniques that can be used to solve the problem. We can write
the algorithm using this strategy.
 It uses the Brute force search to solve the problem, and the brute force search says that
for the given problem, we try to make all the possible solutions and pick out the best
solution from all the desired solutions.
 This rule is also followed in dynamic programming, but dynamic programming is used
for solving optimization problems. In contrast, backtracking is not used in solving
optimization problems.
 Backtracking is used when we have multiple solutions, and we require all those solutions.
 Backtracking name itself suggests that we are going back and coming forward; if it
satisfies the condition, then return success, else we go back again.
 It is used to solve a problem in which a sequence of objects is chosen from a specified
set so that the sequence satisfies some criteria.

When to use a Backtracking algorithm:

Backtracking algorithms are best used to solve problems that have the following
characteristics:
 There are multiple possible solutions to the problem.
 The problem can be broken down into smaller sub problems.
 The sub problems can be solved independently.

State space: State space is the set of paths from root node to other nodes. State space tree is the
tree organization of the solution space. The state space trees are called static trees. This
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

terminology follows from the observation that the tree organizations are independent of the
problem instance being solved.

Terminology related to Backtracking:

Problem state : Problem state is each node in the depth first search tree .

 Solution states: Solution states are the problem states „S‟ for which the path from the
root node to „S‟ defines a tuple in the solution space.
 Answer states : Answer states are those solution states for which the path from root node
to s defines a tuple that is a member of the set of solutions.
 Live node: The nodes that can be further generated are known as live nodes.

 Candidate: A candidate is a potential choice or element that can be added to the

current solution.
 Solution: The solution is a valid and complete configuration that satisfies all problem
constraints.
 Partial Solution: A partial solution is an intermediate or incomplete configuration
being constructed during the backtracking process.
 Decision Space: The decision space is the set of all possible candidates or choices at each
decision point.
 Decision Point: A decision point is a specific step in the algorithm where a candidate is
chosen and added to the partial solution.
 Feasible Solution: A feasible solution is a partial or complete solution that adheres to all
constraints.
 Dead End: A dead end occurs when a partial solution cannot be extended without violating
constraints.
 Backtrack: Backtracking involves undoing previous decisions and returning to a prior
decision point.
 Search Space: The search space includes all possible combinations of candidates and
choices.
 Optimal Solution: In optimization problems, the optimal solution is the best possible
solution.
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Types of Backtracking Problems

Problems associated with backtracking can be categorized into 3 categories:
 Decision Problems: Here, we search for a feasible solution.
 Optimization Problems: For this type, we search for the best solution.
 Enumeration Problems: We find set of all possible feasible solutions to the problems of
this type.
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Backtracking algorithm working Procedure:

1. Choose an initial solution.

2. Explore all possible extensions of the current solution.
3. If an extension leads to a solution, return that solution.
4. If an extension does not lead to a solution, backtrack to the previous solution and try a
different extension.
5. Repeat steps 2-4 until all possible solutions have been explored.

How does Backtracking works:

Backtracking is a systematic method of trying out various sequences of decisions until you find
out that works. Let's understand through an example.

We start with a start node. First, we move to node A. Since it is not a feasible solution so we
move to the next node, i.e., B. B is also not a feasible solution, and it is a dead-end so we
backtrack from node B to node A.
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Suppose another path exists from node A to node C. So, we move from node A to node C. It is
also a dead-end, so again backtrack from node C to node A. We move from node A to the
starting node.

Now we will check any other path exists from the starting node. So, we move from start node to
the node D. Since it is not a feasible solution so we move from node D to node E. The node E is
also not a feasible solution. It is a dead end so we backtrack from node E to node D.

Suppose another path exists from node D to node F. So, we move from node D to node F. Since
it is not a feasible solution and it's a dead-end, we check for another path from node F.
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Suppose there is another path exists from the node F to node G so move from node F to node G.
The node G is a success node.

Backtracking time complexities:

 Exponential (O(K^N))
 Factorial (O(N!))
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

SUM OF SUBSETS: (Using Backtracking Approach)

Subset sum problem is to find subset of elements that are selected from a given set whose sum

adds up to a given number K. We are considering the set contains non-negative values. It is

assumed that the input set is unique (no duplicates are presented).

Given positive numbers wi, 1 ≤ i ≤ n, and m, this problem requires finding all subsets of wi

whose sums are „m‟.

All solutions are k-tuples, 1 ≤ k ≤ n.

{ 2, 9, 10, 1, 99, 3}

We need to find if there is a subset for a given sum say 4: { 1, 3 }

Complexity Analysis

It is intuitive to derive the complexity of sum of the subset problem. In the state-space tree, at
level i, the tree has 2i nodes. So, given n items, the total number of nodes in the tree would be

1 + 2 + 22 + 23 + .. 2n.

T(n) = 1 + 2 + 22 + 23 + .. 2n = 2n+1 – 1 = O(2n)

Thus, sum of sub set problem runs in exponential order.

Sum of Subsets Algorithm :

SUB_SET_PROBLEM(i, sum, W, remSum)

// Description : Solve sub of subset problem using backtracking

// Input :

W: Number for which subset is to be computed

i: Item index

sum : Sum of integers selected so far

remSum : Size of remaining problem i.e. (W – sum)

K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

// Output : Solution tuple X

if
FEASIBLE_SUB_SET(i) == 1
Then

if
(sum == W)
Then

print X[1…i]

end

else

X[i + 1] ← 1

SUB_SET_PROBLEM(i + 1, sum + w[i] + 1, W, remSum – w[i] + 1 )

X[i + 1] ← 0 // Exclude the ith item

SUB_SET_PROBLEM(i + 1, sum, W, remSum – w[i] + 1 )

end

function

FEASIBLE_SUB_SET(i)

If

(sum + remSum ≥ W) AND (sum == W) or (sum + w[i] + 1 ≤ W)

then

return

end

return

1
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Sum of Subsets Algorithm Steps:

1. Start with an empty set.

2. Add the next element from the list to the set.

3. If the subset is having sum M, then stop with that subset as solution.

4. If the subset is not feasible or if we have reached the end of the set, then backtrack through the
subset until we find the most suitable value.

5. If the subset is feasible (sum of subset < M) then go to step 2.

6. If we have visited all the elements without finding a suitable subset and if no backtracking is
possible then stop without solution.

Example:

Consider the sum-of-subset problem, n = 4, Sum = 13, and w = (3, 4, 5, 6). Find a

solution to the problem using backtracking. Show the state-space tree leading to the
solution.Also, number the nodes in the tree in the order of recursion calls.

Sol: Set X = [0, 0, 0, 0]

Set Sum = 0. Sum indicates summation of selected numbers from W.

Step 1 : i = 1, Adding item wi

Sum = Sum + wi = Sum + w1 = 0 + 3 = 3

Sum ≤ M, so add item i to solution set

X[i] = X[1] = 1 ⇒ X =[1, 0, 0, 0]

Step 2 : i = 2, Adding item w2

Sum = Sum + wi = Sum + w2 = 3 + 4 = 7

Sum ≤ M, so add item i to solution set.

K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

X[i] = X[2] = 1 ⇒ X =[1, 1, 0, 0]

Step 3 : i = 3, Adding item w3

Sum = Sum + wi = Sum + w3 = 7 + 5 = 12

Sum ≤ M, so add item i to solution set.

X[i] = X[3] = 1 ⇒ X =[1, 1, 1, 0]

Step 4 : i = 4, Adding item w4

Sum = Sum + wi = Sum + w4 = 12 + 6 = 18

Sum > M, so backtrack and remove the previously added item from the solution set.

X[i] = X[3] = 0 ⇒ X =[1, 1, 0, 0].

Update Sum accordingly. So, Sum = Sum – w3 = 12 – 5 = 7

And don‟t increment i.

Step 5 : i = 4, Adding item w4

Sum = Sum + wi = Sum + w4 = 7 + 6 = 13

Sum = M, so solution is found and add item i to solution set.

X[i] = X[4] = 1 ⇒ X =[1, 1, 0, 1]

A complete state space tree for given data is shown in Fig.

K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

At level i, the left branch corresponds to the inclusion of number wi and the right branch
corresponds to exclusion of number wi. The recursive call number for the node is stated
below the node. Node 8 is the solution node. The bold solid line shows the path to the
output node.

Include: Here include means that we are selecting the element from the array.

Exclude: Here, exclude means that we are rejecting the element from the array.

Example: S = {3,5,6,7} and d = 15, Find the sum of subsets by using backtracking
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Solve the sum of subset problems using backtracking algorithmic strategy for the following
data: n = 4 W =(w1, w2, w3, w4) = (11, 13, 24, 7) and M = 31.

State-space tree for a given problem is shown here:

K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

In the above graph, the black circle shows the correct result. The gray node shows where
the algorithm backtracks. Numbers in the leftmost column indicate elements under
consideration at that level. The left and right branches represent the inclusion and
exclusion of that element, respectively.

We get two solutions:

 {11, 13, 7}
 {24, 7}

Analyze sum of subsets algorithm on data :

M = 35 and
i) w = {5, 7, 10, 12, 15, 18, 20}
ii) w = {20, 18, 15, 12, 10, 7, 5}
iii) w = {15, 7, 20, 5, 18, 10, 12} Are there any discernible differences in the
computing time ?
Solution:
Let us run the algorithm on first instance w = {5, 7, 10, 12, 15, 18, 20}.

Let us run the algorithm on first instance w = {5, 7, 10, 12, 15, 18, 20}.
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

There may be multiple solutions. A state-space tree for the above sequence is shown here: The
number in the leftmost column shows the element under consideration. The left and right
branches in the tree indicate inclusion and exclusion of the corresponding element at that level,
respectively.
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT
K.CHAITANYA DEEPTHI ASST.PROF CSE DEPT

N-QUEENS PROBLEM:

Let us consider, N = 8. Then 8-Queens Problem is to place eight queens on an 8 x 8 chessboard

so that no two “attack”, that is, no two of them are on the same row, column, or diagonal.

All solutions to the 8-queens problem can be represented as 8-tuples (x1, ......... , x8), where xi is

the column of the ith row where the ith queen is placed.

The promising function must check whether two queens are in the same ROW or column or
diagonal:

Suppose two queens are placed at positions (i, j) and (k, l) Then:

Step 1:

Add to the sequence the next number in the sequence 1, 2, . . . , 8 not yet used.

Step 2:

If this new sequence is feasible and has length 8 then STOP with a solution. If the new sequence
K.CHAITANYA DEEPTHI ASST.PROF CSE DEPT

is feasible and has length less then 8, repeat Step 1.

Step 3:

If the sequence is not feasible, then backtrack through the sequence until we find the most recent

place at which we can exchange a value. Go back to Step 1.

K.CHAITANYA DEEPTHI ASST.PROF CSE DEPT

THE 8-QUEENS PROBLEM:

This 8 queens problem is to place n-queens in an ‘N*N’ matrix in such a way that

no two queens attack each otherwise no two queens should be in the same row, column,

diagonal.

Solution:

The solution vector X (X1…Xn) represents a solution in which Xi is the column of

the th row where I th queen is placed.

 First, we have to check no two queens are in same row.

 Second, we have to check no two queens are in same column.
 The function, which is used to check these two conditions, is [I, X (j)], which

gives position of the I th queen, where I represents the row and X (j) represents the column
position.

 Third, we have to check no two queens are in it diagonal.

 Consider two dimensional array A[1:n,1:n] in which we observe that every element on

the same diagonal that runs from upper left to lower right has the same value.

 Also, every element on the same diagonal that runs from lower right to upper left has the
same value.
K.CHAITANYA DEEPTHI ASST.PROF CSE DEPT

 Suppose two queens are in same position (i,j) and (k,l) then two queens lie on the same
diagonal , if and only if |j-l|=|I-k|.

STEPS TO GENERATE THE SOLUTION:

 Initialize x array to zero and start by placing the first queen in k=1 in the first row.
 To find the column position start from value 1 to n, where ‘n’ is the no. of columns or
no. of queens.
 If k=1 then x (k)=1.so (k, x(k)) will give the position of the k th queen. Here we have to
check whether there is any queen in the same row or column or diagonal.
 For this considers the previous position, which had already, been found out. Check

Whether X (I)=X(k) for column |X(i)-X(k)|=(I-k) for the same diagonal.

 If any one of the conditions is true then return false indicating that k th queen can’t be
placed in position X (k).
 For not possible condition increment X (k) value by one and precede d until the position
is found.
 If the position X (k) £ n and k=n then the solution is generated completely.
 If k<n, then increment the ‘k’ value and find position of the next queen.
 If the position X (k)>n then k th queen cannot be placed as the size of the matrix is
‘N*N’.
 So decrement the ‘k’ value by one i.e. we have to back track and after the position of the
previous queen.

Algorithm:
K.CHAITANYA DEEPTHI ASST.PROF CSE DEPT

4-QUEENS PROBLEM USING STATE SPACE TREE:

K.CHAITANYA DEEPTHI ASST.PROF CSE DEPT
K.CHAITANYA DEEPTHI ASST.PROF CSE DEPT
K.CHAITANYA DEEPTHI ASST.PROF CSE DEPT
K.CHAITANYA DEEPTHI ASST.PROF CSE DEPT

Time Complexity:
The algorithm uses backtracking to generate all possible solutions for placing N queens on an
N x N chessboard. The backtracking algorithm recursively explores all possible solutions by
checking whether a queen can be placed in each column of the current row. The time
complexity of the algorithm can be expressed as O(N!) because in the worst case scenario,
every queen must be tried in every column of every row.
Space Complexity:
The space complexity of the algorithm depends on the size of the input problem, which is N. In
the given code, an array ‘arr’ of size N is used to store the column index of the queen in each
row. Additionally, a variable ‘no’ is used to count the number of valid solutions found.
Therefore, the space complexity of the algorithm can be expressed as O(N).
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Graph Coloring Problem

Introduction to Graph Coloring Problem:

Graph coloring refers to the problem of coloring vertices of a graph in such a way that no two
adjacent vertices have the same color. This is also called the vertex coloring problem.

 If coloring is done using at most k colors, it is called k-coloring.

 The smallest number of colors required for coloring graph is called its chromatic
number.

 The chromatic number is denoted by X(G). Finding the chromatic number for the graph
is NP-complete problem.
 Graph coloring problem is both, decision problem as well as an optimization problem. A
decision problem is stated as, “With given M colors and graph G, whether such color
scheme is possible or not?”
 The optimization problem is stated as, “Given M colors and graph G, find the minimum
number of colors required for graph coloring.”

Working procedure for Graph coloring Problem using Backtracking algorithm:

Step1: List down all the vertices and colors in two lists.
Step2: Assign color 1 to vertex 1.
Step3: If vertex 2 is not adjacent to vertex 1 then assign the same color, otherwise assign color 2.
Step4: Repeat the process until all vertices are colored.
Step 5: Algorithm backtracks whenever color i is not possible to assign to any vertex k and it
selects next color i + 1 and test is repeated.
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Graph Coloring Algorithm:

GRAPH_COLORING(G, COLOR, i)

// Description : Solve the graph coloring problem using backtracking

// Input : Graph G with n vertices, list of colors, initial

vertex i

// COLOR[1…n] is the array of n different colors

// Output : Colored graph with minimum color

if

CHECK_VERTEX(i) == 1

then

if

i == N

then

print

COLOR[1…n]

Else

j←1

while

(j ≤ M)

do

COLOR(i + 1) ← j

j←j+1

end

Function
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

CHECK_VERTEX(i)

for

j ← 1 to i – 1

do

if

Adjacent(i, j)

then

if

COLOR(i) == COLOR(j)

then

return

End

Return 1

Example1: Explain the Graph–Coloring problem and Construct state space tree for m= 3
colors and n=4 vertices graph. C0lors=Red,Green,Blue

Sol:
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Example2: Explain the Graph–Coloring problem and Construct state space tree for m= 3
colors and n=4 vertices graph. C0lors=Red,Green,Blue

Sol: If we assign color 1 to vertex A, the same color cannot be assigned to vertex B or C.

 In the next step, B is assigned some different colors 2.

 Vertex A is already colored and vertex D is a neighbor of B, so D cannot be assigned
color 2. The process goes on. State-space tree is shown in Figure:
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Thus, vertices A and C will be colored with color 1, and vertices B and D will be colored
with color 2.

Complexity Analysis:

The number of a node increases exponentially at every level in state space tree. With M colors
and n vertices, total number of nodes in state space tree would be

Thus, the graph coloring algorithm runs in exponential time.

Time and space complexity of the Graph coloring algorithm is :

Example: Construct a planar graph for the following map. Explain how to find m-coloring
of this planar graph by using an m-coloring Backtracking algorithm.

OR

Sol: Area 1 is adjacent to areas 2, 3, and 4. So, in a planar graph, vertex 1 will be connected to
vertices 2, 3, and 4.
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Area 2 is adjacent to areas 1, 3, 4, and 5, so in a planar graph, vertex 2 will be connected to

vertices 1, 3, 4, and 5. This process will be repeated for all areas. Hence, the planar graph would
be:

 This problem can be solved using backtracking algorithms as follows:

 List down all the vertices and colors in two lists
 Assign color 1 to vertex 1
 If vertex 2 is not adjacent to vertex 1 then assign the same color, otherwise assign color 2.
 Repeat the process until all vertices are colored.
The algorithm backtracks whenever color i is not possible to assign to any vertex k and it selects the next
color i + 1 and the test is repeated. This graph can be colored using four different colors. A gray node
indicates backtracking.
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Applications of Graph Coloring Problem:

 Design a timetable.
 Sudoku
 Register allocation in the compiler
 Map coloring

0/1 Knapsack Problem:

Knapsack Problem using Backtracking can be solved as follow:
 The knapsack problem is useful in solving resource allocation problems.
 Let X = <x1, x2, x3, . . . . . , xn> be the set of n items,
W = <w1, w2, w3, . . . , wn> and V = <v1, v2, v3, . . . , vn> be the set of weight and value
associated with each item in X, respectively.
 Let M be the total capacity of the knapsack, i.e. knapsack cannot hold items having a
collective weight greater than M.
 Select items from X such that it maximizes the profit and the collective weight of
selected items does not exceed the knapsack capacity.
 The knapsack problem has two variants. 0/1 knapsack does not allow breaking up
the item, whereas a fractional knapsack does. 0/1 knapsack is also known as a
binary knapsack.
 The Knapsack problem can be formulated as,
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Algorithm for 0/1 Knapsack Problem using Backtracking

The algorithm for binary knapsack using a backtracking approach is described below:

Algorithm

BK_KNAPSACK(M, W, V, fw, fp, X)

// Description : Solve knapsack problem using backtracking

// Input :

M: Knapsack capacity

W(1...n): Set of weight of the items

V(1...n): Set of profits associated with items

Fw: Final knapsack weight

Fp: Final earned profit

X(1...n): Solution vector

N: Total number of items

// Output : Solution tuple X, earned profit fp

// Initialization

cw ← 0 // Current weight

cp ← 0 // Current profit

fp ← – 1

k←1 // Index of item being processed

loop:

while

(k ≤ n) AND (cw + W[k] ≤ M)

do

// Select kth item

K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

cw ← cw + W[k]

cp ← cp + V[k]

Y[k] ← 1

k←k+1

end

if

k>n

then

fp ← cp

fw ← cw

k←n

X←Y

Else

Y[k] ← 0 // weight exceed knapsack capacity so skip item

end

while

BOUND(cp, cw, k) ≤ fp

do

while

k ≠ 0 AND Y[k] ≠ 1

do

k←k–1

end

if

k == 0
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

then

return

end

Y[k] ← 0

cw ← cw – W[k]

cp ← cp – P[k]

end

k←k+1

end loop

Algorithm for BOUND is described here:

Function

BOUND(cp, cw, k)

b ← cp

c ← cw

for

i ← k + 1 to n

do

c ← c + W[i]

if

c<M

then

b ← b + P[i]

else

return

(b + (1 – (c – M)/W[i] * P[i])
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

End return (b)

Example: Consider knapsack problem : n = 8. (W1, W2, W3, W4, W5, W6, W2, W8) = (1, 11,
21, 23, 33, 43, 45, 55), P = (11, 21, 31, 33, 43, 53, 55, 65), m = 110. Solve the problem using
backtracking approach.
Solution:

Here M = 110 and n = 8.

Initially, cp = cw = 0, fp = – 1, k = 0

For k = 1:
cp = cp + p1 = 0 + 11 = 11
cw = cw + w1 = 0 + 1 = 1
cw < M, so select item 1

k = k+1=2

For k=1:
cp = cp + p2 = 11 + 21 = 32
cw = cw + w2 = 1 + 11 = 12
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

cw < M, so select item 2

k = k+1=2

For k = 2:
cp = cp + p3 = 32 + 31 = 63
cw = cw + w3 = 12 + 21 = 33
cw < M, so select item 3

k = k+1=3

For k = 3:
cp = cp + p4 = 63 + 33 = 96
cw = cw + w4 = 33 + 23 = 56
cw < M, so select item 4

k = k+1=4

For k = 4:
cp = cp + p5 = 96 + 43 = 139
cw = cw + w5 = 56 + 33 = 89
cw < M, so select item 5

k = k+1=5

For k = 5:
cp = cp + p6 = 139 + 53 = 192
cw = cw + w6 = 89 + 43 = 132
cw > M, so reject item 6 and find upper bound

cp = cp – p6 = 192 – 53 = 139
cw = cw – w6 = 132 – 43 = 89
ub = cp + ((M – cw ) / w i+1) * pi+1
b = cp + [(110 – 89) / 43] * 53 = 164.88
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Inclusion of any item from {I6, I7, I8} will exceed the capacity. So let’s backtrack to item 4.
The space tree as shown in Fig.

Upper bound at node 1:

ub = cp + ((M – cw ) / w i+1) * pi+1
= 139 + [(110 – 89)] / 43 * 53 = 164.88

Upper bound at node 2:

= 96 + [(110 – 56) / 33] * 43 = 166.09

Upper bound at node 3:

= 63 + [(110 – 33) / 33] * 43 = 163.33
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT

Time Complexity: O(N * W). As redundant calculations of states are avoided.

Auxiliary Space: O(N * W) + O(N). The use of a 2D array data structure for storing
intermediate states and O(N) auxiliary stack space(ASS) has been used for recursion stack.

Recursion Approach for 0/1 Knapsack Problem:

To solve the problem follow the below idea:
A simple solution is to consider all subsets of items and calculate the total weight and profit of
all subsets. Consider the only subsets whose total weight is smaller than W. From all such
subsets, pick the subset with maximum profit.
Optimal Substructure: To consider all subsets of items, there can be two cases for every
item.
 Case 1: The item is included in the optimal subset.
 Case 2: The item is not included in the optimal set.
K.CHAITANYA DEEPTHI ASST.PROF CSE,DEPT