BACKTRACKING APPROACH

01/02/2026 1
 1. 8 QUEENS PROBLEM
2. SUM OF SUBSET PROBLEM
3. GRAPH COLORING PROBLEM
4. HAMILTONIAN CYCLES.
5. 0-1 KNAPSACK PROBLEM

01/02/2026 2
Backtracking is a graph based method for designing of algorithm. In
this method we explore a search tree . We start with a node and
explore the nodes of a search tree in depth-first fashion. However,
all the nodes need not be explored. We cut the branches of the tree
using a function feasible which incorporates the constraints of the
problem. This reduces the time complexity of the algorithm.

Backtracking is a procedure whereby, after determining that a node

can lead to nothing but dead ends , we go back(“backtrack”) to the
node’s parent and proceed with the search on the next child. We
call a node nonpromising if when visiting the node we determine
that it cannot possibly lead to a solution . Otherwise , we call it
promising .

01/02/2026 3
 Recursive backtracking algorithm
Recur_backtrack(int k)
{ // the first k-1 values x[1],x[2],…,x[k-1] have been assigned
1. for(each x[k] in the list L of the possible values for x[k])
2. {
3. if feasible(x[1],x[2],….,x[k] )//whether satisfies the constraints
4. {
5. if feasible(x[1],x[2],….,x[k] gives a solution)
6. print (x[1],x[2],…,x[k]);
7. else
8. Recur_backtrack(int k)
9. }
10. }
11. }
01/02/2026 4
 N QUEENS PROBLEM

01/02/2026 5
 SOLVING 4 QUEENS PROBLEM

01/02/2026 6
 SOLVING 8 QUEEN PROBLEM

01/02/2026 7
 SOLVING 4 QUEENS PROBLEM

01/02/2026 8
 SOLVING 8 QUEENS PROBLEM
If we imagine the chess board squares being numbered as the
indices of the two dimensional array a[1:n,1:n] , then we observe
that every element on the same diagonal that runs from the left
upper to the lower right has the same row-column value. In the
case of a[4,2] , that are diagonal to this queen (running from the
upper left to the lower right) are a[3,1] , a[5,3], a[6,4],a[7,5], and
a[8,6] . All these squares have a row-column value of 2 . Also,
every element on the same diagonal that goes from the upper
right to the lower left has the same row+column value. Suppose
that the 2 queens are placed at position (i,j) and (k,l) . Then by
the above they are on the same diagonal iff
i-j=k-l or i+j=k+l
j-l=i-k j-l=k-1
|j-l|=|k-i|,
Therefore 2 queens lie on the same diagonal iff |j-l|=|k-i|,
01/02/2026 9
 SOLVING 8 QUEENS PROBLEM
The queen in row 6 is
being threatened in its
left diagonal by the
queen in row 3 and in
its right diagonal by the
queen in row 2.

01/02/2026 10
 SOLVING 8 QUEENS PROBLEM
Place(k,i) returns a Boolean value that is true if the kth queen can
be placed in column i. It tests both whether i is a distinct from
all previous values x[1],x[2],…,x[k-1] and whether there is no
other queen on the same diagonal. Its computing time is O(k-1).

Using Place , we can refine the general backtracking method as

given by algorithm and gives a precise solution to the n-queen
problem . The array x[] is global . The algorithm is invoked by
Nqueen(1,n)

01/02/2026 11
 SOLVING 8 QUEENS PROBLEM
Nqueens(k,n)
/* Using backtracking , this procedure prints all possible placements of n
queens on an n*n chessboard so that they are non attacking */
{
for i:=1 to n do
{
if Place(k,i) then
{
x[k]:=i;
if (k=n) then write (x[1:n]);
else Nqueens(k+1,n);
}
}
}
01/02/2026 12
 SOLVING 8 QUEENS PROBLEM
Place (k,i)
/* Returns true if a queen can be placed in the kth row and ith
column. Otherwise it returns false . x[] is a global array whose
first (k-1) values have been set. Abs(r) returns the absolute value
of r. */
{
for j:=1 to k-1 do
if((x[j]==i) or (Abs(x[j]-i)=Abs(j-k)))
/* Two are in the same column or in the same diagonal */
then return false;
return true;
}

01/02/2026 13
 SOLVING 8 QUEENS PROBLEM-FACT SHEET
• BRUTE FORCE SOLUTION WILL CONSIDER 64C8
(=4426165368)POSITIONS OF THE QUEEN
• PLACING THE QUEENS ROW BY ROW ATMOST
8!(=40320) QUEEN POSITION WILL BE
CONSIDERED.
• FUNCTION Nqueens(k,n) IS CALLED ONLY 1965
TIMES FOR N=8.
• FOR 8 QUEEN PROBLEM 92 POSSIBLE
SOLUTIONS ARE THERE.
01/02/2026 14
01/02/2026 15
 ITERATIVE BACKTRACKING ALGORITHM
FOR n-Queens PROBLEM

01/02/2026 16
 GRAPH COLORING PROBLEM

01/02/2026 17
 SOLVING GRAPH COLORING PROBLEM
Let G be a graph and m be a given positive integer. We want to discover
whether the nodes of G can be colored in such a way that no 2 adjacent
nodes have the same color yet only m colors are used. This is termed the m-
colorability decision problem . The m-colorability optimization problem
asked for the smallest integer m for which the graph G can be colored. This
integer is referred to as the chromatic number of the graph.

We are interested in determining all the different ways in which a given graph
can be colored using atmost m colors.

Suppose we represent a graph by its adjacency matrix G[1:n,1:n] , where

G[i,j]=1 if (i,j) is an edge of G , and G[i,j]=0 otherwise. The colors are
represented by the integers 1,2,..m and the solutions are given by the n-
tuple(x1,x2,…xn) , where xi is the color of node i.

Function mColoring is begun by first assigning the graph to its adjacency matrix ,
setting the array[] to zero , and then invoking the statement mColoring(1).
01/02/2026 18
 SOLVING GRAPH COLORING PROBLEM
Function NextValue produces the possible colors for xk after x1
through xk-1 have been defined. The main loop of mColoring
repeatedly picks an element from the set of possibilities ,
assigns it to xk, and then calls mColoring recursively.

Figure shows a simple graph containing 4 nodes . Below that is the

tree that is generated by mColoring . Each path to a leaf
represents a coloring using atmost 3 colors . In this tree , after
choosing x1=2 and x2=1 the possible choices for x3 are 2 and 3 .
After choosing x1=2, x2=1 and x3=2, possible values for x4 are 1
and 3. And so on.

01/02/2026 19
 SOLVING GRAPH COLORING PROBLEM

01/02/2026 20
 SOLVING GRAPH COLORING PROBLEM

State Space tree for mColoring when n=3 and m=3

01/02/2026 21
 SOLVING GRAPH COLORING PROBLEM

A 4-node graph and all possible 3-Colorings

01/02/2026 22
 SOLVING GRAPH COLORING PROBLEM
Algorithm mColoring(k)
/* This algorithm was formed using the recursive backtracking schema. The
graph is represented by its Boolean adjacency matrix G[1:n,1:n]. All
assignments of 1,2,…m to the vertices of the graph such that adjacency
vertices are assigned distinct integers are printed. K is the index of the
next vertex to color. */
8{
9 repeat
10 { // Generate all legal assignment for x[k]
11 NextValue(k); // Assign to x[k] a legal color.
12 if (x[k]=0) then return ; //No new color possible
13 if (k=n) then // At most m colors have been used to
14 // color the n vertices.
15 write(x[1:n])
16 else mColoring(k+1)
17 }until (false);
18 }
01/02/2026 23
 SOLVING GRAPH COLORING PROBLEM
Algorithm NextValue(k)
/* x[1],…x[k-1] have been assigned integer values in the range
[1,m] such that adjacent vertices have distinct integers. A
value for x[k]is determined in the range [0,m].x[k] is
assigned the next highest numbered color while maintaining
distinctness from the adjacent vertices of vertex k. If no such
color exists , then x[k]=0. */

01/02/2026 24
 SOLVING GRAPH COLORING PROBLEM
Algorithm NextValue(k)
8{
9 repeat
10 {
11 x[k]:=(x[k]+1)mod(m+1); // Next highest color.
12 if (x[k]=0) then return ; //All colors have been used.
13 for j:=1 to n do
14 -15 { //Check if this color is distinct from adjacent colors.
16 if ((G(k,j)≠0) and (x[k]=x[j]))
17-18 // If (k,j) is an edge and if adjacent vertices have the
//same color
19 then break;
20 }
21 if (j=n+1) then return ; //New color found
22 } until(false); // Otherwise try to find another color.
23 }
01/02/2026 25
 SOLVING GRAPH COLORING PROBLEM
Rec_graph_color(int k,int C)
{ // Graph is represented by the matrix G[1:n][1:n]. Vertices are
//assigned colors which are represented as integers from
// 1,2,…C. k is the next vertex to color
1. for(x[k]=1;x[k]<=C;x[k]++)
2. if (feasible_color(k)) // check whether the color is feasible
3. if(k==n) // check if the solution is found
4. print(x[1],x[2],…,x[n]); //print solution
5. else
6. Rec_graph_color(k+1,C);
7. } // End of Rec_graph_color(…)

RECURSIVE BACKTRACKING ALGORITHM FOR COLORING A GRAPH

WITH C COLORS
01/02/2026 26
 SOLVING GRAPH COLORING PROBLEM
feasible_color (int k)
{// returns TRUE if kth node can be assigned a color in x[k]
1. int i;
2. for (i=1;i<=k-1;i++) // check the color of previous nodes
3. if ((G[i][k]==TRUE) && (x[i]==x[k]) // check if the nodes
are // same or distinct
4. return FALSE //color clash
5. return TRUE //no color clash
6. } // End of feasible_color (…)

TO CHECK IF THE ASSIGNED COLOR TO THE KTH NODE IS FEASIBLE

OR NOT .

01/02/2026 27
 HAMILTONIAN CYCLES PROBLEM

01/02/2026 28
 SOLVING HAMILTONIAN CYCLES PROBLEM

Let G=(V,E) be a connected graph with n vertices . A Hamiltonian

cycle is a round-trip path along n edges of the G that visits
every vertex once and returns to its starting position.
If a Hamiltonian begins at some vertex v1€G and the vertices of G
are visited in the order v1,v2,…vn+1 , then the edges (vi,vi+1) are in
E ,n≥i≥1 , and the vi are distinct except for v1 and vn+1 , which are
equal.
Graph shown on next slide contains the Hamiltonian cycle
1,2,8,7,6,5,4,3,1 . Another graph contains no Hamiltonian cycle.
We use backtracking algorithm that finds all the Hamiltonian
cycles in a graph. The graph may be directed or undirected .
Only distinct cycles are output.

01/02/2026 29
SOLVING HAMILTONIAN CYCLES PROBLEM

01/02/2026 30
 HAMILTONIAN CIRCUIT{V1V2V8V7V6V5V4V3V1}

01/02/2026 31
01/02/2026 32
 SOLVING HAMILTONIAN CYCLES PROBLEM
The backtracking solution vector (x1,x2,…,xn) is defined so that xi represents
the ith visited vertex of the proposed cycle. Now all we do is to
determine how to compute the set of possible vertices for xk if x1,x2,
…,xk-1 have already been chosen.
If k=1 , then x1 can be any of the n vertices. To avoid printing the same cycle
n times , we require that x1=1. If 1<k<n , then xk can be any vertex v that
is distinct from x1,x2,…,xk-1 and v is connected by an edge to xk-1. The
vertex xn can only be the one remaining vertex and it must be connected
to both xn-1 and x1.
We begin by presenting function NextValue(k) which determines a possible
next vertex for the proposed cycle.
Using NextValue we can particularize the recursive backtracking schema to
find all Hamiltonian cycles . This algorithm is started by first initializing
the adjacency matrix G[1:n,1:n] then setting x[2:n] to zero and x[1]=1 ,
and then executing Hamiltonian(2).
TSP is also a Hamiltonian cycle . For the simple case of a graph all of whose edges
costs are identical , Hamiltonian will find a minimum-cost tour if a tour exists.
If the common edge cost is c , the cost of a tour is cn since there are n edges33 in
01/02/2026
 SOLVING HAMILTONIAN CYCLES PROBLEM

Algorithm NextValue(k)
/* x[1:k-1] is a path of k-1 distinct vertices. If x[k]=0 , then no
vertex has as yet been assigned to x[k]. After execution , x[k]
is assigned to the next highest numbered vertex which does
not already appear in x[1:k-1] and is connected by an edge
to x[k-1] . Otherwise x[k]=0 .If k=n , then in addition x[k] is
connected to x[1]. */

01/02/2026 34
 SOLVING HAMILTONIAN CYCLES PROBLEM
Algorithm NextValue(k)
8{
9 repeat
10 {
11 x[k]:=(x[k]+1)mod(n+1); //Next vertex
12 if(x[k]=0) then return ;
13 if(G[x[k-1],x[k]]≠0) then
14 { // Is there an edge ?
15 for j:=1 to k-1do if (x[j]=x[k]) then break;
16 // Check for distinctness
17 if (j=k) then // If true , then the vertex is distinct.
18 if((k<n) or ((k=n) and G[x[n],x[1]]≠0)
19 then return;
20 }
21 } until(false);
22 }
01/02/2026 35
 SOLVING HAMILTONIAN CYCLES PROBLEM

Algorithm Hamiltonian(k)
/* This algorithm uses the recursive formulation of
backtracking to find all the Hamiltonian cycles of a graph .
The graph is stored as an adjacency matrix G[1:n,1:n] All
cycles begin at node 1. */
6. {
7. repeat
8. {// Generate values for x[k]
9. NextValue(k); // Assign a legal next value to x[k]
10. if (x[k]=0) then return ;
11. if (k=n) then write (x[1:n])
12. else Hamiltonian (k+1);
13. } until(false);
14. }
01/02/2026 36
 RECURSIVE BACKTRACKING ALGORITHM FOR FINDING HAMILTONIAN CYCLES IN A GRAPH

Rec_Hamiltonian(int k)
{ // Finds Hamiltonian cycles in a graph
1. for (x[k]=2;x[k]<=n;x[k]++)
2. if (feasible_node(k))// check whether the node is feasible
3. if(k==n) //check if solution is found
4. print(x[1],x[2],….,x[n]); //print solution
5. else
6. Rec_Hamiltonian(k+1); //Explore Further
7. } // End of Rec_Hamiltonian(…)

01/02/2026 37
 To check if the next node x[k] on the Hamiltonian path is feasible
feasible_node(int k) or not
{// returns TRUE if kth node on the Hamiltonian path can be node in x[k]
1. int i;
2. if((G[x[k-1]][x[k]]==TRUE)
3. {
4. for(i=1;i<=k-1;i++) //check the previous nodes
5. if (x[i]==x[k]) //check for distinctness
6. return FALSE
7. if((k<n) || ((k==n) && (G[x[k-1]][x[k]]==TRUE))
8. return TRUE
9. else
10. return FALSE
11. }
12. else
13. return FALSE;
14. } // End of the feasible_node(…)
01/02/2026 38
 SUM OF SUBSETS PROBLEM

01/02/2026 39
 SOLVING SUM OF SUBSETS PROBLEM
Resembling some what like 0-1 Knapsack problem , suppose all the
items have same profit per unit weight . Then the optimal solution for
the thief would simply be a set of items that maximized the total
weight , subject to the constraint that its total weight did not exceed
W. The thief might first try to determine whether there was a set
whose total weight equaled W , because this would be best. The
problem of determining such sets is called the Sum-Of-Subsets
problem.
In this problem , there are n positive integers (weights)wi,
and a positive integer W . The goal is to find all subsets of the integers
that sum to W.
Suppose n=5,W=21 and w1=5,w2=6,w3=10,w4=11 and w5=16
Because w1+w2+w3=5+6+10=21
w1+w5=5+16=21
w3+w4=10+11=21
Therefore
01/02/2026
the solutions are {w1,w2,w3},}{w1,w5} and {w3,w4} 40
 SOLVING SUM OF SUBSETS PROBLEM
For solving a problem a state space tree can be created. We go to the
left from the root to include w1,and we go to the right to exclude w1 .
Similarly, we go to the left from the node at level 1 to include w2, and
we go to the right to exclude w2 etc. Each subset is represented by a
path from the root to a leaf. When we include wi, we write wi on the
edge where we include it. When we do not include wi, we write 0.

A state space tree for Sum-Of-Subset problem in which n=3.

01/02/2026 41
Example ::n=3 and W=6 with w1=2,w2=4 and w3=5.
At each node , we have written the sum of the weights that have
been included up to that point . Therefore, each leaf contains the
sum of the weights in the subset leading to that leaf. The second
leaf from the left is the only one containing 6. Because the path
to this leaf represents the subset {w1,w2} , this subset is the only
solution.
01/02/2026 42
 The pruned state space tree produced
using backtracking for the example.
Stored at each node is the total weight
included up to that node . The only
solution is found at the shaded node .
Each nonpromising node is marked with
a cross. There are 15 nodes (out of 31 in
the entire state space tree) in this
pruned state space tree.

Above figure shows the pruned state space tree when backtracking is used with
n=4,W=13 and w1=3 w2=4 w3=5 and w4=6.
The only solution is found at the node shaded in color which is {w1,w2,w4}. The
nonpromising nodes are marked with crosses . The nodes containing 12,8and 9
are nonpromising because adding their next weight (6) would make the value of
weight exceed W . The nodes containing 7,3,4 and 0 are nonpromising because
there is not enough total weight remainining to bring the value of weight up to
W. A leaf in the state space tree that does not contain a solution is automaticlly
nonpromising because there are no weights remaining that could bring weight
upto W[leaf containing 7].
01/02/2026 43
 SOLVING SUM OF SUBSETS PROBLEM
Suppose we are given n distinct positive numbers (usually called
weights) and we desire to find all combination of these numbers
whose sum are m. This is called the sum of subsets problem.
In this case the element xi of the solution vector is either one or
zero depending on whether the weight wi is included or not. For
the node at level “i” the left child corresponds to xi=1 and the
right to xi=0.
A simple choice for the bounding function is Bk(x1,x2,…,xk)=true iff

Clearly x1,…xk cannot lead to an answer node if the condition is not

satisfied. The bounding function can be strengthened if we
assume the wi’s are initially in nondecreasing order. In this case
x1,x2,…xk cannot lead to answer node if
01/02/2026 44
 SOLVING SUM OF SUBSETS PROBLEM
The bounding function we use are therefore Bk(x1,x2,…,xk)=true iff

Figure on the next slide shows the portion of the state space tree generated by
function SumOfSub while working on the instance n=6, m=30 and
w[1:6]={5,10,12,13,15,18}. The rectangular nodes lists the values of s,k and r on
each of the calls to SumOfSub . Circular nodes represent points at which
subsets with sums m are printed out . At nodes A,B and C the outputs are
respectively (1,1,0,0,1) ,(1,0,1,1) and (0,0,1,0,0,1) . The tree contains only 23
rectangular nodes . The full state space tree for n=6 contains 26-1 =63 nodes
from which calls could be made (this call excludes the 64 leaf nodes as no call
need to be made from a leaf)
01/02/2026 45
 SOLVING SUM OF SUBSETS PROBLEM

01/02/2026 46
Algorithm SumOfSub:

The algorithm SumOfSub is a recursive implementation that efficiently solves the Sum
of Subsets problem.

1. Input: s (current sum), k (current index), r (remaining sum)

2. Goal: Find all subsets of w[1:n] that sum to m
3. Assumptions:

w[1] ≤ m and Σw[i] ≥ m

w[j]'s are in non-decreasing order
s = Σ(w[j] * x[j]) for 1 ≤ j < k
r = Σw[j] for j ≥ k

01/02/2026 47
 4. Algorithm steps:

a. Generate left child (include w[k]):

Set x[k] = 1
If s + w[k] = m, write the subset (solution found)
Else if s + w[k] + w[k+1] ≤ m,
recursively call SumOfSub(s + w[k], k + 1, r - w[k])

b. Generate right child (exclude w[k]):

If (s + r - w[k] ≥ m) and (s + w[k+1] ≤ m):
Set x[k] = 0
Recursively call SumOfSub(s, k + 1, r - w[k])

The algorithm avoids computing sums repeatedly by keeping track of s and r. It

also includes optimizations to reduce unnecessary recursive calls and prune the
search space effectively.

01/02/2026 48
 SOLVING SUM OF SUBSETS PROBLEM

Algorithm SumOfSub(s,k,r)
/* This algorithm finds all subsets of w[1:n] that sum to m. The
values of x[j] , 1<=j<k, have already been determined .The w[j]’s
are in nondecreasing order.. */

01/02/2026 49
 SOLVING SUM OF SUBSETS PROBLEM
Algorithm SumOfSub(s,k,r)
6. {
7. // Generate left child . Note s+w[k]<=m since B k-1 is true.
8. x[k]:=1;
9. if (s+w[k]=m ) then write (x[1:k]) // Subset found
10. // There is no recursive call here as w[j]>0, 1<=j<=n.
11. else if (s+w[k]+w[k+1] <=m)
12. then SumOfSub (s+w[k],k+1,r-w[k]) ;
13. // Generate right child and evaluate Bk.
14. if((s+r-w[k] >=m) and (s+w[k+1]<=m) )then
15. {
16. x[k]:=0;
17. SumOfSub(s,k+1,r-w[k])
18. }
19. }
01/02/2026 50
 SOLVING SUM OF SUBSETS PROBLEM--NEAPOLITAN

We present the algorithm that employs these strategies . The

algorithm uses an array include. It sets include[i] to “yes” if w[i]
is to be included and to “no” if it is not.
Problem :: Given n positive integers (weights) and a positive
integer W , determine all combinations of the integers that sum
to W.
Inputs :: Positive integer n , sorted (nondecreasing order) array of
positive integers w indexed from 1 to n , and a positive integer
W.
Outputs :: All combinations of the integers that sum to W.

01/02/2026 51
 SOLVING SUM OF SUBSETS ALGORITHM BY --NEAPOLITAN
void sum_of_subsets( index i, int weight , int total)
{// initial call will be sum_of_subsets(0,0,total);
if (promising(i))
if (weight==W)
print( include[1] through include[i]);
else
{
include[i+1]=“yes”;
sum_of_subsets(i+1,weight +w[i+1],total-w[i+1]);
include[i+1]=“no”;
sum_of_subsets(i+1,weight ,total-w[i+1]);
}
}
bool promising (index i)
{
return (weight + total >=W) && (weight ==W || weight + w[i+1]<=W)
}

01/02/2026 52
 SOLVING SUM OF SUBSETS PROBLEM

sum_of_subset(int S,int n,int t )

{ // The sum of subsets is S, n is the number of integers , k is
the //position in solution vector.
1. if (k<=n)
2. for (x[k]=0;x[k]<=1;x[k]++) // assign 0 and 1 values to x[k]
3. if (feasible(k))
4. if(ik1 pi x i ==S)
5. print_solution(k);
6. else
7. sum_of_subset(S,n,k+1);
8. else
9. return;
10. } // End of sum_of_subset(…..)

01/02/2026 53
 SOLVING SUM OF SUBSETS PROBLEM

feasible(int k )
{1. int i, sum,remsum;
2. sum=0;
3. remsum=0;
4. for(i=1;i<=k-1;i++)
5. sum=sum+p[i]*x[i];
6. for(i=k;i<=n;i++)
7. remsum=remsum+p[i];
8. if((sum+p[k]>S) || (sum+remsum<S))
9. return false;
10. return true.
11. } // End of feasible(…..)

01/02/2026 54
 0-1 KNAPSACK PROBLEM

01/02/2026 55
 SOLVING 0-1 KNAPSACK PROBLEM

We solve the problem using a state space tree , we go to the left from to root to include
the first item , and we got to the right to exclude it. Similarly, we go to the left from a node
at level 1 to include the second item , and we go to the right to exclude it, and so on. Each
path from the root to a leaf is a candidate solution.
It is a optimization problem which means that we do not know if a node contains a solution
until the search is over. If the items included up to a node have a greater total profit than
the best solution so far, we change the value of the best solution so far. However, we may
find a better solution at one of the node’s descendants(by stealing more items). Therefore,
for optimization problems we always visit a promising node’s children. The following is a
general algorithm for backtracking in the case of optimization problems.
void checknode(node v)
{ node u;
if(value(v) is better than best)
best=value(v);
if(promising(v))
for(each child u of v)
checknode(u); }

01/02/2026 56
 SOLVING 0-1 KNAPSACK PROBLEM
The variable best has the value of the best solution found so far , and value(v) is
the value of the solution at the node. After best is initiated to a value that is
worse than the value of any candidate solution , the root is passed at the top
level. A node is promising only if we should expand to its children.
A node is nonpromising is that there is no capacity left in the knapsack for more
items. Therefore, if weight is the sum of the weights of the items that have been
included upto some node, the node is nonpromising if
weight >=W.
It is nonpromising even if weight equals W because, in the case of optimization
problems , “promising” means that we should expand to the children.
We first order the items in nonincreasing order according to the values of pi/wi ,
where pi and wi are profits and weights respectively of the ith item. Suppose we
are trying to determine whether a particular node is promising . We can obtain
an upper bound on the profit that could be obtained by expanding beyond that
node as follows. Let profit be the sum of the profits of the items included upto
the node . weight is the sum of weights of these items. We initialize variables
bound and totweight to profit and weight respectively. Next we greedily grab
items , adding their profits to bound and their weights to totweight , until we get
an item that if grabbed would bring totweight above W.
01/02/2026 57
 SOLVING 0-1 KNAPSACK PROBLEM

We grab the fraction of that item allowed by the remaining weight , and we add
the value of that fraction to bound. If we are able to get only a fraction of the
last weight , this node cannot lead to a profit equal to bound, but bound is
still an upper bound on the profit we could achieve by expanding beyond the
node. Suppose the node is at level i, and the node at level k is one that would
bring the sum of the weights above W. Then
k1
totweight = weight +  wj
j i 1
k1
• and bound =(profit +  j i 1
pj ) + (W-totweight) * (pi/wi)
If maxprofit is the value of the profit in the best solution found so far , then a
node at level i is nonpromising if bound<=maxprofit.

01/02/2026 58
 SOLVING 0-1 KNAPSACK PROBLEM

• Suppose we have the instance of 0-1 knapsack problem with n=4 , W=16 and
we have the following
• i pi wi pi/wi
• 1 40 2 20
• 2 30 5 06
• 3 50 10 05
• 4 10 5 02

The items are ordered according to pi/wi. Figure on the next slide shows the
pruned state space tree produced by using backtracking . The total profit,
total weight , and bound are specified from top to bottom at each node. Each
node is labeled with its level and its position from left in the tree. For
example , the shaded node is labeled (3,3) because it is at level 3 and it is the
third node from the left at that level . Now we present the steps that
produced the pruned tree . In these steps we refer to the node by its label.

01/02/2026 59
01/02/2026 60
1. Set maxprofit to 0.
2. Visit node(0,0) (the root)
a. Compute its profit and weight
profit=0.
weight =0.
b. Compute its bound. Because 2+5+10=17, and 17>16 , the value of W ,
the third item would bring the sum of the weights above W. Therefore , k=3
and we have 3 1
totweight = weight +  w
j 0 1 j
= 0+2+5=7.
3 1
bound =(profit +  p ) + (W-totweight) * (p3/w3)
j 0 1 j
= 0+40+30+(16-7) *50/10=115
c. Determine that the node is promising because its weight 0 is less than
16, the value of W ,and its bound 115 is greater than 0 , the value of
maxprofit.

01/02/2026 61
3. Visit node(1,1)
a. Compute its profit and weight
profit=0 + 40=40.
weight =0+2=2
b. Because its weight 2 is less than or equal to 16, the value of W , and
its profit 40 is greater than 0 , the value of maxprofit , set maxprofit to
40 .
c. Compute its bound. Because 2+5+10 =17, and 17>16 , the value of W,
the third would bring the sum of weights above W. Therefore, k=3,
and we have
3 1
totweight = weight +  w
j 11 j
= 2+5=7.
3 1
bound =(profit +
 j 11
p ) + (W-totweight) * (p3/w3)
j
= 40+30+(16-7) *50/10=115
d. Determine that the node is promising because its weight 2 is less than
16, the value of W ,and its bound 115 is greater than 40 , the value
of maxprofit.

01/02/2026 62
4. Visit node(2,1)
a. Compute its profit and weight
profit=40 + 30=70.
weight =2+5=7
b. Because its weight 7 is less than or equal to 16, the value of W , and
its profit 70 is greater than 40 , the value of maxprofit , set maxprofit to
70 .
c. Compute its bound. we have
3 1
totweight = weight +
= 2+5=7.
 w
j 2 1 j

bound = 70+(16-7) *50/10=115

d. Determine that the node is promising because its weight 7 is less than
16, the value of W ,and its bound 115 is greater than 70 , the value
of maxprofit.

01/02/2026 63
5. Visit node(3,1)
a. Compute its profit and weight
profit=70 + 50=120.
weight =7+10=17
b. Because its weight 17 is greater than 16, the value of W , and maxprofit
does not change .
c. Determine that it is nonpromising because its weight 17 is greater than
or equal to 16, the value of W.
d. The bound for this node is not computed , because its weight has
determined it to be nonpromising.

01/02/2026 64
6. Backtrack to node (2,1).
7. Visit node(3,2)
a. Compute its profit and weight. Because we are not including item 3
profit=70
weight =7
b. Because its profit 70 is less than or equal to 70 maxprofit, maxprofit
does not change .
c. Compute its bound. The fourth weight would not bring the sum of
items above W , and there are only 4 items . Therefore k=5, and

5 1
bound = profit +  j 31
pj = 70+10=80.

d. Determine that the node is promising because its weight 7 is less than
16, the value of W ,and its bound 80 is greater than 70 , the value
of maxprofit.

01/02/2026 65
8. Visit node(4,1)
a. Compute its profit and weight to be 80 and 12.
b. Because its weight 12 is less than or equal to 16, the value of W ,and its
profit 80 is greater than 70 , the value of maxprofit, set maxprofit
to 80.
c. Compute its bound to be 80. = 70+10=80.
d. Determine that it is nonpromising because its bound 80 is less than
or equal to 80, the value of maxprofit. Leaves in the state
space tree are automatically nonpromising because their bounds are
always less than or equal to maxprofit.
9. Backtrack to node(3,2)
10. Visit node(4,2)
a. Compute its profit and weight to be 70 and 7.
b. Compute its bound to be 70.
c. Determine that the node is nonpromising because its bound 70 is less
than or equal to 80 , the value of maxprofit.
11. Backtrack to node(1,1)

01/02/2026 66
12. Visit node(2,2)
a. Compute its profit and weight to be 40 and 2.
b. Compute its bound to be 98.
c. Determine that it is promising because its weight 2 is less than 16, the
value of W ,and its bound 98 is greater than 80 ,the value of
maxprofit.
13. Visit node(3,3)
a. Compute its profit and weight to be 90 and 12.
b. Because its weight 12 is less than or equal to 16, the value of W ,and its
profit 90 is greater than 80 , the value of maxprofit, set maxprofit to
90.
c. Compute its bound to be 98.
d. Determine that it is promising because its weight 12 is less than 16, the
value of W , and its bound 98 is greater than 90 , the value of
maxprofit.
14. Visit node(4,3).
a. Compute its profit and weight to be 100 and 17.
b. Determine that it is nonpromising because its weight 17 is greater than
or equals to 16 , the value of W.
01/02/2026 c. The bound for this node is not computed because its weight has 67
15. Backtrack to node(3,3)
16. Visit node(4,4)
a. Compute its profit and weight to be 90 and 12.
b. Compute its bound to be 90.
c. Determine that it is nonpromising because its bound 90 is less than or
equal to 90 , the value of maxprofit.
17 . Backtrack to node(2,2)
18. Visit node(3,4).
a. Compute its profit and weight to be 40 and 2.
b. Compute its bound to be 50.
c. Determine that it is nonpromising because its bound 50 is less than or
equal to 90 , the value of maxprofit.
19. Backtrack to root.
20. Visit node(1,2)
a. Compute its profit and weight to be 0 and 0.
b. Compute its bound to be 82.
c. Determine that it is nonpromising because its bound 82 is less than or
equal to 90 , the value of maxprofit.
21.01/02/2026
Backtrack to root. (a). Root has no more children. We are done. 68
 ALGORITHM
Problem ::Let n items be given, where each item has a weight >0 and a
profit>[Link] a set of items with maximum total profit, under the
constraint that the sum of their weights cannot exceed W.

Inputs :: Positive integers n and W ; arrays w and p , each indexed from 1 to n ,

and each containing positive integers sorted in nonincreasing order according
to the values of p[i]/w[i].

Outputs ::An array bestset indexed from 1 to n , where the values of bestset[i] is
“yes” if the ith item is included in the optimal set and is “no” otherwise; an
integer maxprofit that is the maximum profit.

ALGORITHM CONTINUED ON NEXT SLIDE

01/02/2026 69
void knapsack(index i, int profit,int weight)
{ if(weight<=W &&profit>maxprofit)
{ maxprofit=profit;
numberset=i; //Set numberset to be number of items
considered
bestset=include; // Set bestset to this solution.
}
if(promising(i))
{ include[i+1]=“YES”;
knapsack(i+1,profit+p[i+1],weight+w[i+1]); //Include w[i+1]
include[i+1]=“NO”;
knapsack(i+1,profit,weight); //Do not include w[i+1]
}
}

ALGORITHM CONTINUED ON NEXT SLIDE

01/02/2026 70
bool promising (index i)
{ index j,k;
int totweight;
float bound;
if (weight>W) // Node is promising only if we should expand to its children.
return FALSE;
else
{ j=i+1;
bound=profit;
totweight=weight;
while(j<=n && totweight+w[j] <=W) // Grab as many items as possible.
{
totweight=totweight+w[j];
bound=bound+p[j];
j++;
}
k=j;
if(k<=n)
bound=bound + (W-totweight)*p[k]; // Grab fraction of kth item.
return bound>maxprofit;
}}

01/02/2026 71
 Continued

The following code would produce the maximum profit and a set that has
the profit .
numbest=maxprofit=0;
knapsack(0,0,0);
cout<< maxprofit;
for(j=1;j<=numbest;j++)
cout<<bestset[i];

Leaves in the state space tree are automatically non promising because
their bounds cannot be greater than maxprofit. Therefore, we should
not need a check for a terminal condition that i=n in function
promising. If i=n , bound does not change from its initial value profit.
Because profit is less than or equal to maxprofit, the expression
bound>maxprofit is false , which means that function promising
returns false.

01/02/2026 72
 Continued

Our upper bound does not change value as we repeatedly

proceed to the left in the state space tree until we reach the
node at level k. Therefore each time a value of k is established ,
we can save its value and proceed to the left without calling
function promising until we reach the node at the (k-1)st level.
We know that the left child of its node in nonpromising because
including the kth item would bring the value of weight above W.
Therefore, we proceed only to the right from this node . It is only
after a move to the right that we need to call function promising
and determine a new value of k.

01/02/2026 73