LAB $3$

$[$PLO K$2,$ CLO $2\mathrm{.}2]$

Topic: Brute Force Algorithms

$1.$ Exhaustive Search: Knapsack Problem

$2.$ Exhaustive Search: Travel Salesperson Problem

$3.$ Validation Knapsack Problem Code

$4.$ Validation of Travel Salesperson Code

Student Name: $\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

Student ID: $\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

Exercise $1$: $($Exhaustive Search: Knapsack Problem$)$

Example of a one$-$dimensional knapsack problem:

In Fig. $1,$ which boxes should be placed in the bag to

maximize the value $($amount of money$)$ while keeping the

overall weight under or equal to $15$ kg$?$ The solution is

that we will pick all boxes except the green box. In this

case the total weigh of the Knapsack will be $8$ Kg and the

value of the picked items will be $$15($which is the

maximum you can have$).$

The exhaustive search approach is that you try all

possible combinations and find the items that will have

maximum overall value and also fit in the knapsack.

Implement this approach in the language of your choice.

The code will take following inputs:

$$ The capacity of the knapsack: C

$$ The weights of the available items: W$,$ which should be an Nx$1$ vector, where N is

the number of available items, and W$($i$)=$ weight of item i$.$

$$ The values of the available items: V$,$ which should be an Nx$1$ vector, and V$($i$)=$

value of item i$.$

The code will have the following outputs:

Kingdom of Saudi Arabia

Ministry of Education

University of Jeddah

College of Science and Computer Engineering

$$

$$

$$

$$

Fig. $1$: Knapsack Problem

$$ The items picked: P$,$ which is a Nx$1$ vector such that P$($i$)=0$ if item i is not picked

and P$($i$)=1$ if item i is picked. For example, P $=[1,0,0,1,1]$ means that items $1,4,$

and $5$ are picked.

$$ Total value of the picked items

$$ Total weight of the picked items

function $[$items$,$ wt$,$ vt$]=$ BF$\_$knapsack$($w$,$ v$,$ capacity$)$

$\%$ w $=[11,1,2,1,4]$;

$\%$ v $=[4,2,2,1,10]$;

$\%$ capacity $=15$;

n $=$ numel$($w$)$;

vt$=0$; $\%$total value

wt$=0$; $\%$total weight

items$=0$; $\%$picked items

S $=$ dec$2$bin$(0$:$2^$n $-1)-\text{'}0\text{'}$; $\%$ all possible exhaustive search

options

for i$=1$:size$($S$,1)$

j $=$ S$($i$,$:$)$; $\%$get a possible combinition in S

j $=$ find$($j$==1)$; $\%$indices of picked items in this

combinition

w$1=$ sum$($w$($j$))$; $\%$picked weight

if w$1>$capacity, continue; end $\%$infeasible solution

v$1=$ sum$($v$($j$))$; $\%$picked weight

if v$1>$vt $\%$store if this cominition is best so

far

vt$=$v$1$;

wt$=$w$1$;

items$=$j;

end

end

end

PART B: Run your code for the following inputs:

C $=15$

W $=[11,2,1,4,1]$

V $=[4,2,1,10,2]$

Write the output of your code below:

Items Picked P $=[0,1,1,1]$

Total value of picked items $=15$

Total weight of picked items $=8$

Exercise $2$: $($Exhaustive Search: Travel Salesperson Problem$)$

PART A: A salesman need to travel to all nodes shown in Figure on

right, starting from the first node $1$ and coming back to the same

place. Each node is visited only once. Distance from each node to

every other node is also shown in the figure. You can represent this

graph in the form of matrix given below.

D $=$

$0285$

$2034$

$8$

$5$

$3$

$4$

$0$

$7$

$7$

$0$

Rows and columns correspond to nodes in order and an element D$($i$,$ j$)$ represents the

distance between node i and j$.$

One way to solve this problem is to perform Exhaustive Search, i$.$e$.,$ we try all possible

routes and find which one is the shortest.

You are required to implement this algorithm, in the language of your choice. The

algorithm should have the following inputs:

$$ A NxN distance matrix D$.$ The element D$($i$,$j$)$ gives distance from node i to j$,$ and

distance from a node i to itself D$($i$,$i$)=0.$

The code's outputs should be:

$$ The best route $($the numbers of nodes in the order in which they are traversed$).$ For

example $14231$ represents traveling from node $1$ to $4$ to $2$ to $3$ to $1.$

$$ The minimum distance traveled by the salesperson

function $[$best$\_$path,min$\_$d$]=$ travel$\_$sales$\_$person$($dm$)$

$\%$dm$=[0,2,8,5$;$2,0,3,4$;$8,3,0,7$;$5,4,7,0]$; $\%$ for debugging

$\%$ number of nodes

n $=$ size$($dm$,1)$;

nodes $=1$:n;

$\%$ possible paths

paths $=$ repmat$($nodes$(1),$ factorial$($n$-1),$ n$+1)$;

paths$($:$,2$:end$-1)=$ perms$($nodes$(2$:n$))$;

$\%$ distances for all paths

min$\_$d $=$ Inf;

for i$=1$:size$($paths$,1)$

p $=$ paths$($i$,$:$)$;

d $=0$;

for j$=2$:numel$($p$)$

d$=$d$+$dm$($p$($j$-1),$p$($j$))$;

end

if d $<$ min$\_$d

min$\_$d $=$ d;

best$\_$path $=$ p;

end

end

disp$($best$\_$path$)$;

disp$($min$\_$d$)$;

end

PART B: Run your code for the distance matrix given in Part A and write the output below.

the best path: $14321$

minimum distance: $17$

Exercise $3$: $($Validation Knapsack Problem Code$)$

You will be provided an input. Run you code in Exercise $1$ on this input and write your

answers in the provided space on blackboard.

Exercise $4$: $($Validation TSP Problem Code$)$

You will be provided an input. Run you code in Exercise $2$ on this input and write your

answers in the provided space on blackboard.