18BCE0294

YASH KUMAR

DATA STRUCTURES AND ALGORITHMS

LAB ASSIGNMENT-6

NAME- YASH KUMAR

REGISTRATION NUMBER-18BCE0294

PSEUDOCODE-
INPUT- total number of vertices, adjacency matrix, starting
node, ending node
OUTPUT- the shortest path and the cost of shortest path
void dijkstra(int a[size][size],int n,int startnode, int endnode)
{
int cost[size][size],distance[size],pr[size];
int visited[size],count,mindistance,next,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i][j]==0)
cost[i][j]=infinite;
else
cost[i][j]=a[i][j];
for(i=0;i<n;i++)
{
distance[i]=cost[startnode][i];
pr[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
18BCE0294
YASH KUMAR

while(count<n-1)
{
mindistance=infinite;

for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i])
{
mindistance=distance[i];
next=i;
}

visited[next]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[next][i]<distance[i])
{
distance[i]=mindistance+cost[next][i];
pr[i]=next;
}
count++;
}
for(i=0;i<n;i++)
if(i==endnode)
{
printf("\nDistance of node%d=%d",i,distance[i]);
printf("\nPath=%d",i);
j=i;
do
{
j=pr[j];
printf("<-%d",j);
}while(j!=startnode);
}
}
18BCE0294
YASH KUMAR

CODE-
#include<stdio.h>
#define infinite 9999
#define size 10

void dijkstra(int a[size][size],int n,int startnode, int endnode)

{
int cost[size][size],distance[size],pr[size];
int visited[size],count,mindistance,next,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i][j]==0)
cost[i][j]=infinite;
else
cost[i][j]=a[i][j];
for(i=0;i<n;i++)
{
distance[i]=cost[startnode][i];
pr[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1)
{
mindistance=infinite;

for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i])
{
18BCE0294
YASH KUMAR

mindistance=distance[i];
next=i;
}

visited[next]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[next][i]<distance[i])
{
distance[i]=mindistance+cost[next][i];
pr[i]=next;
}
count++;
}
for(i=0;i<n;i++)
if(i==endnode)
{
printf("\nDistance of node%d=%d",i,distance[i]);
printf("\nPath=%d",i);
j=i;
do
{
j=pr[j];
printf("<-%d",j);
}while(j!=startnode);
}
}

int main()
{
int a[size][size],i,j,n,u,des;
printf("Enter no. of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
18BCE0294
YASH KUMAR

for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
printf("\nEnter the starting node:");
scanf("%d",&u);
printf("\nEnter the destination node:");
scanf("%d",&des);
dijkstra(a,n,u,des);
return 0;
}
18BCE0294
YASH KUMAR

KNAPSACK PROBLEM
In this dynamic programming problem we have n items each with
an associated weight and value (benefit or profit). The objective is
to fill the knapsack with items such that we have a maximum profit
without crossing the weight limit of the knapsack. Since this is a 0 1
knapsack problem hence we can either take an entire item or reject
it completely. We can not break an item and fill the knapsack.

SOLVING METHOD:
 In this problem we have a Knapsack that has a weight limit W.
 There are items i1, i2, ..., in each having weight w1, w2, … wn
and some benefit (value or profit) associated with it v1, v2, ...
vn
 Our objective is to maximise the benefit such that the total
weight inside the knapsack is at most W.
 Since this is a 0 1 Knapsack problem algorithm so, we can
either take an entire item or reject it completely. We can not
break an item and fill the knapsack.

Problem
Assume that we have a knapsack with max weight capacity W = 5
Our objective is to fill the knapsack with items such that the benefit
(value or profit) is maximum.
Following table contains the items along with their value and weight.
ITEM I 1 2 3 4

VALUE VAL 100 20 60 40

WEIGHT WT 3 2 4 1

Total items n = 4
Total capacity of the knapsack W = 5
Now we create a value table V[i,w] where, i denotes number of
items and w denotes the weight of the items.
Rows denote the items and columns denote the weight.
18BCE0294
YASH KUMAR

As there are 4 items so, we have 5 rows from 0 to 4.

And the weight limit of the knapsack is W = 5 so, we have 6
columns from 0 to 5
V[I,W] W=0 1 2 3 4 5

I=0

We fill the first row i = 0 with 0. This means when 0 item is

considered weight is 0.
Then we fill the first column w = 0 with 0. This means when weight
is 0 then items considered is 0.
Rule to fill the V[i,w] table.
if wt[i] > w then
V[i,w] = V[i-1,w]

else if wt[i] <= w then

V[i,w] = max( V[i-1,w], val[i] + V[i-1, w - wt[i]] )

After calculation, the value table V

V[I,W] W=0 1 2 3 4 5

I=0 0 0 0 0 0 0

1 0 0 0 100 100 100

2 0 0 20 100 100 120

3 0 0 20 100 100 120

4 0 40 40 100 140 140

18BCE0294
YASH KUMAR

Maximum value earned

Max Value = V[n,W]
= V[4,5]
= 140
Items that were put inside the knapsack
are found using the following rule

set i = n and w = W

while i and w > 0 do

if V[i,w] != V[i-1,w] then
mark the ith item
set w = w - wt[i]
set i = i - 1
else
set i = i - 1
endif
endwhile

So, items we are putting inside the knapsack are 4 and 1.

18BCE0294
YASH KUMAR

C Code:-

#include<stdio.h>

void knapSack(int W, int n, int val[], int wt[]);

int getMax(int x, int y);

int main(void) {

int val[] = {-1, 100, 20, 60, 40}; //value of the items

int wt[] = {-1, 3, 2, 4, 1}; //weight of the items

int n = 4; //total items

int W = 5; //capacity of knapsack

knapSack(W, n, val, wt);

return 0;

int getMax(int x, int y) {

if(x > y) {

return x;

else {

return y;

}
18BCE0294
YASH KUMAR

void knapSack(int W, int n, int val[], int wt[]) {

int i, w;

int V[n+1][W+1]; //value table having n+1 rows and W+1

columns

for(w = 0; w <= W; w++) {

V[0][w] = 0; //fill the row i=0 with value 0

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

V[i][0] = 0; //fill the column w=0 with value 0

for(i = 1; i <= n; i++) //fill the value table

{ for(w = 1; w <= W; w++)

{ if(wt[i] <= w) {

V[i][w] = getMax(V[i-1][w], val[i] + V[i-1][w - wt[i]]);

else {

V[i][w] = V[i-1][w];

printf("Max Value: %d\n", V[n][W]); //max value that can be put inside the
knapsack