Using book Machine learning an algorithmic perspectiove sec

Using book Machine learning - an algorithmic perspectiove second edition , Stephen Marsland
Generic algorithm: https://seat.massey.ac.nz/personal/s.r.marsland/Code/Ch10/ga.py
Four Peaks alg: https://seat.massey.ac.nz/personal/s.r.marsland/Code/Ch10/fourpeaks.py
Knapsack problem: https://seat.massey.ac.nz/personal/s.r.marsland/Code/Ch10/knapsack.py

Use the genetic algorithm to solve the Knapsack Problem on p. 222 of the text book. You are to modify the Python codes provided for the Four Peaks problem on pp. 222-224 of the textbook with the specified parameters to work with the fitness function for the provided knapsack problem. Experiment with different values of the unspecified parameters and run the algorithm for a sufficient number of (at least 5) times until some different solutions are obtained. Report the parameters used in the experiments reaching the different results.

What modifications would be done to the python codes with specified parameteres to work with the firness funtion for the provided knapsack problem? Please explain what parameters used and why.

Solution

import sys

def knapsk(itms, maxwgt):
  
bstval = [[0] * (maxwgt + 1)
for i in xrange(len(itms) + 1)]

for i, (val, wgt) in enumerate(itms):

i += 1
for capacty in xrange(maxwgt + 1):
  
if wgt > capacty:
bstval[i][capacty] = bstval[i - 1][capacty]
else:

candid1 = bstval[i - 1][capacty]
candid2 = bstval[i - 1][capacty - wgt] + val
bstval[i][capacty] = max(candid1, candid2)

reconstruction = []
i = len(itms)
j = maxwgt
while i > 0:
if bstval[i][j] != bstval[i - 1][j]:
reconstruction.append(itms[i - 1])
j -= itms[i - 1][1]
i -= 1

reconstruction.reverse()

return bstval[len(itms)][maxwgt], reconstruction

if __name__ == \'__main__\':
if len(sys.argv) != 2:
print(\'usage: knapsack.py [file]\')
sys.exit(1)

filename = sys.argv[1]
with open(filename) as f:
lines = f.readlines()

maxwgt = int(lines[0])
itms = [map(int, line.split()) for line in lines[1:]]

bestvalue, reconstruction = knapsk(itms, maxwgt)

print(\'Best possible value: {0}\'.format(bstval))
print(\'Items:\')
for val, wgt in reconstruction:
print(\'V: {0}, W: {1}\'.format(val, wgt))