Chapter 41: Breadth-First Search

Section 41.1: Finding the Shortest Path from Source to other

Nodes
Breadth-first-search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the
tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor
nodes first, before moving to the next level neighbors. BFS was invented in the late 1950s by Edward Forrest Moore,
who used it to find the shortest path out of a maze and discovered independently by C. Y. Lee as a wire routing
algorithm in 1961.

The processes of BFS algorithm works under these assumptions:

1. We won't traverse any node more than once.

2. Source node or the node that we're starting from is situated in level 0.
3. The nodes we can directly reach from source node are level 1 nodes, the nodes we can directly reach from
level 1 nodes are level 2 nodes and so on.
4. The level denotes the distance of the shortest path from the source.

Let's see an example:

Let's assume this graph represents connection between multiple cities, where each node denotes a city and an
edge between two nodes denote there is a road linking them. We want to go from node 1 to node 10. So node 1 is
our source, which is level 0. We mark node 1 as visited. We can go to node 2, node 3 and node 4 from here. So
they'll be level (0+1) = level 1 nodes. Now we'll mark them as visited and work with them.

[Link] – Algorithms Notes for Professionals 190

The colored nodes are visited. The nodes that we're currently working with will be marked with pink. We won't visit
the same node twice. From node 2, node 3 and node 4, we can go to node 6, node 7 and node 8. Let's mark them
as visited. The level of these nodes will be level (1+1) = level 2.

[Link] – Algorithms Notes for Professionals 191

If you haven't noticed, the level of nodes simply denote the shortest path distance from the source. For example:
we've found node 8 on level 2. So the distance from source to node 8 is 2.

We didn't yet reach our target node, that is node 10. So let's visit the next nodes. we can directly go to from node 6,
node 7 and node 8.

[Link] – Algorithms Notes for Professionals 192

We can see that, we found node 10 at level 3. So the shortest path from source to node 10 is 3. We searched the
graph level by level and found the shortest path. Now let's erase the edges that we didn't use:

[Link] – Algorithms Notes for Professionals 193

After removing the edges that we didn't use, we get a tree called BFS tree. This tree shows the shortest path from
source to all other nodes.

So our task will be, to go from source to level 1 nodes. Then from level 1 to level 2 nodes and so on until we reach
our destination. We can use queue to store the nodes that we are going to process. That is, for each node we're
going to work with, we'll push all other nodes that can be directly traversed and not yet traversed in the queue.

The simulation of our example:

First we push the source in the queue. Our queue will look like:

front
+-----+
| 1 |
+-----+

The level of node 1 will be 0. level[1] = 0. Now we start our BFS. At first, we pop a node from our queue. We get
node 1. We can go to node 4, node 3 and node 2 from this one. We've reached these nodes from node 1. So
level[4] = level[3] = level[2] = level[1] + 1 = 1. Now we mark them as visited and push them in the queue.

front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+

[Link] – Algorithms Notes for Professionals 194

Now we pop node 4 and work with it. We can go to node 7 from node 4. level[7] = level[4] + 1 = 2. We mark node 7
as visited and push it in the queue.

front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+

From node 3, we can go to node 7 and node 8. Since we've already marked node 7 as visited, we mark node 8 as
visited, we change level[8] = level[3] + 1 = 2. We push node 8 in the queue.

front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+

This process will continue till we reach our destination or the queue becomes empty. The level array will provide us
with the distance of the shortest path from source. We can initialize level array with infinity value, which will mark
that the nodes are not yet visited. Our pseudo-code will be:

Procedure BFS(Graph, source):

Q = queue();
level[] = infinity
level[source] := 0
[Link](source)
while Q is not empty
u -> [Link]()
for all edges from u to v in Adjacency list
if level[v] == infinity
level[v] := level[u] + 1
[Link](v)
end if
end for
end while
Return level

By iterating through the level array, we can find out the distance of each node from source. For example: the
distance of node 10 from source will be stored in level[10].

Sometimes we might need to print not only the shortest distance, but also the path via which we can go to our
destined node from the source. For this we need to keep a parent array. parent[source] will be NULL. For each
update in level array, we'll simply add parent[v] := u in our pseudo code inside the for loop. After finishing BFS,
to find the path, we'll traverse back the parent array until we reach source which will be denoted by NULL value.
The pseudo-code will be:

Procedure PrintPath(u): //recursive | Procedure PrintPath(u): //iterative

if parent[u] is not equal to null | S = Stack()
PrintPath(parent[u]) | while parent[u] is not equal to null
end if | [Link](u)
print -> u | u := parent[u]
| end while
| while S is not empty
| print -> [Link]
| end while

[Link] – Algorithms Notes for Professionals 195

Complexity:

We've visited every node once and every edges once. So the complexity will be O(V + E) where V is the number of
nodes and E is the number of edges.

Section 41.2: Finding Shortest Path from Source in a 2D graph

Most of the time, we'll need to find out the shortest path from single source to all other nodes or a specific node in
a 2D graph. Say for example: we want to find out how many moves are required for a knight to reach a certain
square in a chessboard, or we have an array where some cells are blocked, we have to find out the shortest path
from one cell to another. We can move only horizontally and vertically. Even diagonal moves can be possible too.
For these cases, we can convert the squares or cells in nodes and solve these problems easily using BFS. Now our
visited, parent and level will be 2D arrays. For each node, we'll consider all possible moves. To find the distance to
a specific node, we'll also check whether we have reached our destination.

There will be one additional thing called direction array. This will simply store the all possible combinations of
directions we can go to. Let's say, for horizontal and vertical moves, our direction arrays will be:

+----+-----+-----+-----+-----+
| dx | 1 | -1 | 0 | 0 |
+----+-----+-----+-----+-----+
| dy | 0 | 0 | 1 | -1 |
+----+-----+-----+-----+-----+

Here dx represents move in x-axis and dy represents move in y-axis. Again this part is optional. You can also write
all the possible combinations separately. But it's easier to handle it using direction array. There can be more and
even different combinations for diagonal moves or knight moves.

The additional part we need to keep in mind is:

If any of the cell is blocked, for every possible moves, we'll check if the cell is blocked or not.
We'll also check if we have gone out of bounds, that is we've crossed the array boundaries.
The number of rows and columns will be given.

Our pseudo-code will be:

Procedure BFS2D(Graph, blocksign, row, column):

for i from 1 to row
for j from 1 to column
visited[i][j] := false
end for
end for
visited[source.x][source.y] := true
level[source.x][source.y] := 0
Q = queue()
[Link](source)
m := [Link]
while Q is not empty
top := [Link]
for i from 1 to m
temp.x := top.x + dx[i]
temp.y := top.y + dy[i]
if temp is inside the row and column and top doesn't equal to blocksign
visited[temp.x][temp.y] := true
level[temp.x][temp.y] := level[top.x][top.y] + 1
[Link](temp)

[Link] – Algorithms Notes for Professionals 196

 end if
end for
end while
Return level

As we have discussed earlier, BFS only works for unweighted graphs. For weighted graphs, we'll need Dijkstra's
algorithm. For negative edge cycles, we need Bellman-Ford's algorithm. Again this algorithm is single source
shortest path algorithm. If we need to find out distance from each nodes to all other nodes, we'll need Floyd-
Warshall's algorithm.

Section 41.3: Connected Components Of Undirected Graph

Using BFS
BFS can be used to find the connected components of an undirected graph. We can also find if the given graph is
connected or not. Our subsequent discussion assumes we are dealing with undirected [Link] definition of a
connected graph is:

A graph is connected if there is a path between every pair of vertices.

Following is a connected graph.

Following graph is not connected and has 2 connected components:

1. Connected Component 1: {a,b,c,d,e}

2. Connected Component 2: {f}

[Link] – Algorithms Notes for Professionals 197

BFS is a graph traversal algorithm. So starting from a random source node, if on termination of algorithm, all nodes
are visited, then the graph is connected,otherwise it is not connected.

PseudoCode for the algorithm.

boolean isConnected(Graph g)
{
BFS(v)//v is a random source node.
if(allVisited(g))
{
return true;
}
else return false;
}

C implementation for finding the whether an undirected graph is connected or not:

#include<stdio.h>
#include<stdlib.h>
#define MAXVERTICES 100

void enqueue(int);
int deque();
int isConnected(char **graph,int noOfVertices);
void BFS(char **graph,int vertex,int noOfVertices);
int count = 0;
//Queue node depicts a single Queue element
//It is NOT a graph node.
struct node
{
int v;
struct node *next;
};

typedef struct node Node;

typedef struct node *Nodeptr;

Nodeptr Qfront = NULL;

Nodeptr Qrear = NULL;
char *visited;//array that keeps track of visited vertices.

int main()

[Link] – Algorithms Notes for Professionals 198

{
int n,e;//n is number of vertices, e is number of edges.
int i,j;
char **graph;//adjacency matrix

printf("Enter number of vertices:");

scanf("%d",&n);

if(n < 0 || n > MAXVERTICES)

{
fprintf(stderr, "Please enter a valid positive integer from 1 to %d",MAXVERTICES);
return -1;
}

graph = malloc(n * sizeof(char *));

visited = malloc(n*sizeof(char));

for(i = 0;i < n;++i)

{
graph[i] = malloc(n*sizeof(int));
visited[i] = 'N';//initially all vertices are not visited.
for(j = 0;j < n;++j)
graph[i][j] = 0;
}

printf("enter number of edges and then enter them in pairs:");

scanf("%d",&e);

for(i = 0;i < e;++i)

{
int u,v;
scanf("%d%d",&u,&v);
graph[u-1][v-1] = 1;
graph[v-1][u-1] = 1;
}

if(isConnected(graph,n))
printf("The graph is connected");
else printf("The graph is NOT connected\n");
}

void enqueue(int vertex)

{
if(Qfront == NULL)
{
Qfront = malloc(sizeof(Node));
Qfront->v = vertex;
Qfront->next = NULL;
Qrear = Qfront;
}
else
{
Nodeptr newNode = malloc(sizeof(Node));
newNode->v = vertex;
newNode->next = NULL;
Qrear->next = newNode;
Qrear = newNode;
}
}

int deque()
{

[Link] – Algorithms Notes for Professionals 199

 if(Qfront == NULL)
{
printf("Q is empty , returning -1\n");
return -1;
}
else
{
int v = Qfront->v;
Nodeptr temp= Qfront;
if(Qfront == Qrear)
{
Qfront = Qfront->next;
Qrear = NULL;
}
else
Qfront = Qfront->next;

free(temp);
return v;
}
}

int isConnected(char **graph,int noOfVertices)

{
int i;

//let random source vertex be vertex 0;

BFS(graph,0,noOfVertices);

for(i = 0;i < noOfVertices;++i)

if(visited[i] == 'N')
return 0;//0 implies false;

return 1;//1 implies true;

}

void BFS(char **graph,int v,int noOfVertices)

{
int i,vertex;
visited[v] = 'Y';
enqueue(v);
while((vertex = deque()) != -1)
{
for(i = 0;i < noOfVertices;++i)
if(graph[vertex][i] == 1 && visited[i] == 'N')
{
enqueue(i);
visited[i] = 'Y';
}
}
}

For Finding all the Connected components of an undirected graph, we only need to add 2 lines of code to the BFS
function. The idea is to call BFS function until all vertices are visited.

The lines to be added are:

printf("\nConnected component %d\n",++count);

//count is a global variable initialized to 0
//add this as first line to BFS function

[Link] – Algorithms Notes for Professionals 200

AND

printf("%d ",vertex+1);
add this as first line of while loop in BFS

and we define the following function:

void listConnectedComponents(char **graph,int noOfVertices)

{
int i;
for(i = 0;i < noOfVertices;++i)
{
if(visited[i] == 'N')
BFS(graph,i,noOfVertices);

}
}

[Link] – Algorithms Notes for Professionals 201

Chapter 42: Depth First Search
Section 42.1: Introduction To Depth-First Search
Depth-first search is an algorithm for traversing or searching tree or graph data structures. One starts at the root
and explores as far as possible along each branch before backtracking. A version of depth-first search was
investigated in the 19th century French mathematician Charles Pierre Trémaux as a strategy for solving mazes.

Depth-first search is a systematic way to find all the vertices reachable from a source vertex. Like breadth-first
search, DFS traverse a connected component of a given graph and defines a spanning tree. The basic idea of depth-
first search is methodically exploring every edge. We start over from a different vertices as necessary. As soon as
we discover a vertex, DFS starts exploring from it (unlike BFS, which puts a vertex on a queue so that it explores
from it later).

Let's look at an example. We'll traverse this graph:

We'll traverse the graph following these rules:

We'll start from the source.

No node will be visited twice.
The nodes we didn't visit yet, will be colored white.
The node we visited, but didn't visit all of its child nodes, will be colored grey.
Completely traversed nodes will be colored black.

Let's look at it step by step:

[Link] – Algorithms Notes for Professionals 202

[Link] – Algorithms Notes for Professionals 203
[Link] – Algorithms Notes for Professionals 204
We can see one important keyword. That is backedge. You can see. 5-1 is called backedge. This is because, we're
not yet done with node-1, so going from another node to node-1 means there's a cycle in the graph. In DFS, if we
can go from one gray node to another, we can be certain that the graph has a cycle. This is one of the ways of
detecting cycle in a graph. Depending on source node and the order of the nodes we visit, we can find out any edge
in a cycle as backedge. For example: if we went to 5 from 1 first, we'd have found out 2-1 as backedge.

The edge that we take to go from gray node to white node are called tree edge. If we only keep the tree edge's and
remove others, we'll get DFS tree.

In undirected graph, if we can visit a already visited node, that must be a backedge. But for directed graphs, we
must check the colors. If and only if we can go from one gray node to another gray node, that is called a backedge.

In DFS, we can also keep timestamps for each node, which can be used in many ways (e.g.: Topological Sort).

1. When a node v is changed from white to gray the time is recorded in d[v].

[Link] – Algorithms Notes for Professionals 205

 2. When a node v is changed from gray to black the time is recorded in f[v].

Here d[] means discovery time and f[] means finishing time. Our pesudo-code will look like:

Procedure DFS(G):
for each node u in V[G]
color[u] := white
parent[u] := NULL
end for
time := 0
for each node u in V[G]
if color[u] == white
DFS-Visit(u)
end if
end for

Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
if color[v] == white
parent[v] := u
DFS-Visit(v)
end if
end for
color[u] := black
time := time + 1
f[u] := time

Complexity:

Each nodes and edges are visited once. So the complexity of DFS is O(V+E), where V denotes the number of nodes
and E denotes the number of edges.

Applications of Depth First Search:

Finding all pair shortest path in an undirected graph.

Detecting cycle in a graph.
Path finding.
Topological Sort.
Testing if a graph is bipartite.
Finding Strongly Connected Component.
Solving puzzles with one solution.

[Link] – Algorithms Notes for Professionals 206

Chapter 43: Hash Functions
Section 43.1: Hash codes for common types in C#
The hash codes produced by GetHashCode() method for built-in and common C# types from the System
namespace are shown below.

Boolean

1 if value is true, 0 otherwise.

Byte, UInt16, Int32, UInt32, Single

Value (if necessary casted to Int32).

SByte
((int)m_value ^ (int)m_value << 8);

Char
(int)m_value ^ ((int)m_value << 16);

Int16
((int)((ushort)m_value) ^ (((int)m_value) << 16));

Int64, Double

Xor between lower and upper 32 bits of 64 bit number

(unchecked((int)((long)m_value)) ^ (int)(m_value >> 32));

UInt64, DateTime, TimeSpan

((int)m_value) ^ (int)(m_value >> 32);

Decimal
((((int *)&dbl)[0]) & 0xFFFFFFF0) ^ ((int *)&dbl)[1];

Object
[Link](this);

The default implementation is used sync block index.

String

Hash code computation depends on the platform type (Win32 or Win64), feature of using randomized string
hashing, Debug / Release mode. In case of Win64 platform:

int hash1 = 5381;

int hash2 = hash1;
int c;
char *s = src;
while ((c = s[0]) != 0) {
hash1 = ((hash1 << 5) + hash1) ^ c;
c = s[1];
if (c == 0)
break;
hash2 = ((hash2 << 5) + hash2) ^ c;
s += 2;
}

[Link] – Algorithms Notes for Professionals 207

return hash1 + (hash2 * 1566083941);

ValueType

The first non-static field is look for and get it's hashcode. If the type has no non-static fields, the hashcode of the
type returns. The hashcode of a static member can't be taken because if that member is of the same type as the
original type, the calculating ends up in an infinite loop.

Nullable<T>
return hasValue ? [Link]() : 0;

Array
int ret = 0;
for (int i = (Length >= 8 ? Length - 8 : 0); i < Length; i++)
{
ret = ((ret << 5) + ret) ^ [Link](GetValue(i));
}

References

GitHub .Net Core CLR

Section 43.2: Introduction to hash functions

Hash function h() is an arbitrary function which mapped data x ∈ X of arbitrary size to value y ∈ Y of fixed size: y
= h(x). Good hash functions have follows restrictions:

hash functions behave likes uniform distribution

hash functions is deterministic. h(x) should always return the same value for a given x

fast calculating (has runtime O(1))

In general case size of hash function less then size of input data: |y| < |x|. Hash functions are not reversible or in
other words it may be collision: ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2). X may be finite or infinite set and Y is
finite set.

Hash functions are used in a lot of parts of computer science, for example in software engineering, cryptography,
databases, networks, machine learning and so on. There are many different types of hash functions, with differing
domain specific properties.

Often hash is an integer value. There are special methods in programmning languages for hash calculating. For
example, in C# GetHashCode() method for all types returns Int32 value (32 bit integer number). In Java every class
provides hashCode() method which return int. Each data type has own or user defined implementations.

Hash methods

There are several approaches for determinig hash function. Without loss of generality, lets x ∈ X = {z ∈ ℤ: z ≥
0} are positive integer numbers. Often m is prime (not too close to an exact power of 2).

Method Hash function

Division method h(x) = x mod m
Multiplication method h(x) = ⌊m (xA mod 1)⌋, A ∈ {z ∈ ℝ: 0 < z < 1}
Hash table

Hash functions used in hash tables for computing index into an array of slots. Hash table is data structure for

[Link] – Algorithms Notes for Professionals 208

implementing dictionaries (key-value structure). Good implemented hash tables have O(1) time for the next
operations: insert, search and delete data by key. More than one keys may hash to the same slot. There are two
ways for resolving collision:

1. Chaining: linked list is used for storing elements with the same hash value in slot

2. Open addressing: zero or one element is stored in each slot

The next methods are used to compute the probe sequences required for open addressing

Method Formula
Linear probing h(x, i) = (h'(x) + i) mod m
Quadratic probing h(x, i) = (h'(x) + c1*i + c2*i^2) mod m
Double hashing h(x, i) = (h1(x) + i*h2(x)) mod m

Where i ∈ {0, 1, ..., m-1}, h'(x), h1(x), h2(x) are auxiliary hash functions, c1, c2 are positive auxiliary
constants.

Examples

Lets x ∈ U{1, 1000}, h = x mod m. The next table shows the hash values in case of not prime and prime. Bolded
text indicates the same hash values.

x m = 100 (not prime) m = 101 (prime)

723 23 16
103 3 2
738 38 31
292 92 90
61 61 61
87 87 87
995 95 86
549 49 44
991 91 82
757 57 50
920 20 11
626 26 20
557 57 52
831 31 23
619 19 13
Links

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms.

Overview of Hash Tables

Wolfram MathWorld - Hash Function

[Link] – Algorithms Notes for Professionals 209

Chapter 44: Travelling Salesman
Section 44.1: Brute Force Algorithm
A path through every vertex exactly once is the same as ordering the vertex in some way. Thus, to calculate the
minimum cost of travelling through every vertex exactly once, we can brute force every single one of the N!
permutations of the numbers from 1 to N.

Psuedocode

minimum = INF
for all permutations P

current = 0

for i from 0 to N-2

current = current + cost[P[i]][P[i+1]] <- Add the cost of going from 1 vertex to the next

current = current + cost[P[N-1]][P[0]] <- Add the cost of going from last vertex to the
first

if current < minimum <- Update minimum if necessary

minimum = current

output minimum

Time Complexity

There are N! permutations to go through and the cost of each path is calculated in O(N), thus this algorithm takes
O(N * N!) time to output the exact answer.

Section 44.2: Dynamic Programming Algorithm

Notice that if we consider the path (in order):

(1,2,3,4,6,0,5,7)

and the path

(1,2,3,5,0,6,7,4)

The cost of going from vertex 1 to vertex 2 to vertex 3 remains the same, so why must it be recalculated? This result
can be saved for later use.

Let dp[bitmask][vertex] represent the minimum cost of travelling through all the vertices whose corresponding
bit in bitmask is set to 1 ending at vertex. For example:

dp[12][2]

12 = 1 1 0 0
^ ^
vertices: 3 2 1 0

Since 12 represents 1100 in binary, dp[12][2] represents going through vertices 2 and 3 in the graph with the path
ending at vertex 2.

[Link] – Algorithms Notes for Professionals 210

Thus we can have the following algorithm (C++ implementation):

int cost[N][N]; //Adjust the value of N if needed

int memo[1 << N][N]; //Set everything here to -1
int TSP(int bitmask, int pos){
int cost = INF;
if (bitmask == ((1 << N) - 1)){ //All vertices have been explored
return cost[pos][0]; //Cost to go back
}
if (memo[bitmask][pos] != -1){ //If this has already been computed
return memo[bitmask][pos]; //Just return the value, no need to recompute
}
for (int i = 0; i < N; ++i){ //For every vertex
if ((bitmask & (1 << i)) == 0){ //If the vertex has not been visited
cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]); //Visit the vertex
}
}
memo[bitmask][pos] = cost; //Save the result
return cost;
}
//Call TSP(1,0)

This line may be a little confusing, so lets go through it slowly:

cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);

Here, bitmask | (1 << i) sets the ith bit of bitmask to 1, which represents that the ith vertex has been visited. The
i after the comma represents the new pos in that function call, which represents the new "last" vertex.
cost[pos][i] is to add the cost of travelling from vertex pos to vertex i.

Thus, this line is to update the value of cost to the minimum possible value of travelling to every other vertex that
has not been visited yet.

Time Complexity

The function TSP(bitmask,pos) has 2^N values for bitmask and N values for pos. Each function takes O(N) time to
run (the for loop). Thus this implementation takes O(N^2 * 2^N) time to output the exact answer.

[Link] – Algorithms Notes for Professionals 211

Chapter 45: Knapsack Problem
Section 45.1: Knapsack Problem Basics
The Problem: Given a set of items where each item contains a weight and value, determine the number of each to
include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as
possible.

Pseudo code for Knapsack Problem

Given:

1. Values(array v)
2. Weights(array w)
3. Number of distinct items(n)
4. Capacity(W)

for j from 0 to W do:

m[0, j] := 0
for i from 1 to n do:
for j from 0 to W do:
if w[i] > j then:
m[i, j] := m[i-1, j]
else:
m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

A simple implementation of the above pseudo code using Python:

def knapSack(W, wt, val, n):

K = [[0 for x in range(W+1)] for x in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i==0 or w==0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))

Running the code: Save this in a file named [Link]

$ python [Link]
220

Time Complexity of the above code: O(nW) where n is the number of items and W is the capacity of knapsack.

Section 45.2: Solution Implemented in C#

public class KnapsackProblem
{

[Link] – Algorithms Notes for Professionals 212

 private static int Knapsack(int w, int[] weight, int[] value, int n)
{
int i;
int[,] k = new int[n + 1, w + 1];
for (i = 0; i <= n; i++)
{
int b;
for (b = 0; b <= w; b++)
{
if (i==0 || b==0)
{
k[i, b] = 0;
}
else if (weight[i - 1] <= b)
{
k[i, b] = [Link](value[i - 1] + k[i - 1, b - weight[i - 1]], k[i - 1, b]);
}
else
{
k[i, b] = k[i - 1, b];
}
}
}
return k[n, w];
}

public static int Main(int nItems, int[] weights, int[] values)

{
int n = [Link];
return Knapsack(nItems, weights, values, n);
}
}

[Link] – Algorithms Notes for Professionals 213