Use the following python code to solve the next problems:

$"""$

Program for local searches implemented by me

Knapsack problem

State: $(1$k$1$p$,1$k$2$p$,2$k$,4$k$,12$k$)$

$01234$

Values: $(1,2,2,10,4)$

Dictionary for the values of each product

$"""$

import simpleai.search as ss

from simpleai.search.local import $\_$exp$\_$schedule

# Possible scheduler for simulated$\_$annealing, based on the aima example.

class Knap$($ss$.$SearchProblem$)$:

def $\_$init$\_($self$)$:

# Maximum load of the knapsack

self.$\_$maxLoadKnap $=15$

# Initialize the initial state in the parent class

super$($Knap$,$ self$).\_$init$\_($initial$\_$state$=$self.generate$\_$random$\_$state$())$

def knapsack$\_$weight$($self$,$ cur$\_$state$)$:

weight $=$ cur$\_$state$[0]*1+$ cur$\_$state$[1]*1+\backslash$

cur$\_$state$[2]*2+$ cur$\_$state$[3]*4+$ cur$\_$state$[4]*12$

return weight

def actions$($self$,$ cur$\_$state$)$:

$"""$Returns the actions available to perform from state"""

actions$\_$list $=[]$

# Check if the rule can be triggered in the current state

# before adding it to the list of possible actions

if $($self$.$knapsack$\_$weight$($cur$\_$state$)+1)<=$ self.$\_$maxLoadKnap:

actions$\_$list.append$("1$k$1$p$")$

if $($self$.$knapsack$\_$weight$($cur$\_$state$)+1)<=$ self.$\_$maxLoadKnap:

actions$\_$list.append$("1$k$2$p$")$

if $($self$.$knapsack$\_$weight$($cur$\_$state$)+2)<=$ self.$\_$maxLoadKnap:

actions$\_$list.append$("2$k$")$

if $($self$.$knapsack$\_$weight$($cur$\_$state$)+4)<=$ self.$\_$maxLoadKnap:

actions$\_$list.append$("4$k$")$

if $($self$.$knapsack$\_$weight$($cur$\_$state$)+12)<=$ self.$\_$maxLoadKnap:

actions$\_$list.append$("12$k$")$

return actions$\_$list

def result$($self$,$ cur$\_$state, action$)$:

$"""$Returns the resulting state of applying action to state"""

if action $=="1$k$1$p$"$:

cur$\_$state$[0]+=1$

elif action $=="1$k$2$p$"$:

cur$\_$state$[1]+=1$

elif action $=="2$k$"$:

cur$\_$state$[2]+=1$

elif action $=="4$k$"$:

cur$\_$state$[3]+=1$

elif action $=="12$k$"$:

cur$\_$state$[4]+=1$

return cur$\_$state

def value$($self$,$ cur$\_$state$)$:

$\text{'}\text{'}\text{'}$Returns the value of state as it is needed by optimization

problems.

Value is a number $($integer or floating point$).\text{'}\text{'}\text{'}$

value $=$ cur$\_$state$[0]*1+$ cur$\_$state$[1]*2+\backslash$

cur$\_$state$[2]*2+$ cur$\_$state$[3]*10+$ cur$\_$state$[4]*4$

return value

def generate$\_$random$\_$state$($self$)$:

$"""$

Generates a random state for genetic search. It's mainly used for the

seed states in the initialization of genetic search.

$"""$

import random

state$\_$list $=[0,0,0,0,0]$

weight $=100$

while weight $>$ self.$\_$maxLoadKnap:

state$\_$list$[0]=$ random.randint$(0,$ self.$\_$maxLoadKnap$)$

state$\_$list$[1]=$ random.randint$(0,$ self.$\_$maxLoadKnap$)$

state$\_$list$[2]=$ random.randint$(0,($self$.\_$maxLoadKnap $//2))$

state$\_$list$[3]=$ random.randint$(0,$ self.$\_$maxLoadKnap $//4)$

state$\_$list$[4]=$ random.randint$(0,$ self.$\_$maxLoadKnap $//12)$

weight $=$ self.knapsack$\_$weight$($state$\_$list$)$

return state$\_$list

temp $=50$

def temperature$($time$)$: # CORRECT: IT SHOULD BE A SCHEDULER

# Need to receive time and return a value

# As required by the simulated$\_$annealing function in the library

# global temp

res $=$ temp $-$ time

print$("$Temperature: $",$ time, res$)$

return res

if $\_$name$\_==\text{'}\_$main$\_\text{'}$:

# Initialize the object

problem $=$ Knap$()$

# Solve problem

# output $=$ ss$.$hill$\_$climbing$($problem$)$

# output $=$ ss$.$hill$\_$climbing$\_$stochastic$($problem$)$

output $=$ ss$.$hill$\_$climbing$\_$random$\_$restarts$($problem$,500)$ # the one that runs better

# output $=$ ss$.$simulated$\_$annealing$($problem$,$ temperature$)$

# output $=$ ss$.$simulated$\_$annealing$($problem$,\_$exp$\_$schedule$)$

# The path is a single element since it is not being saved, it doesn't matter to know it

print$(\text{'}$

Path to the solution:$\text{'})$

for item, state in output.path$()$:

print$($state$)$

print$($f$"$Value $=\{$problem$.$value$($state$)\}")$

print$($f$"$Weight $=\{$problem$.$knapsack$\_$weight$($state$)\}")$

$1.$ Use the simple hill$-$climbing algorithm to solve the problem.

Compare the performance of this algorithm with the solution with simulated annealing. What algorithm allows you to find a solution to the problem?

$2.$ Modify the code to now have a "backpack" that supports $50$ kilos and wants to store the greatest possible value of the following elements:

$2$ kilos, $$5$

$1$ kilo, $$2$

$1$ kilo, $$3$

$7$ kilos, $$13$

$3$ kilos, $$10$

$5$ kilos, $$15$

What is the best allocation of items for the backpack? Justify your answer with the results of at least two types of algorithms.