Question

a) Implement the bottom-up dynamic programming algorithm for the knapsack problem in python. The
program should read inputs from a file called “data.txt”, and the output will be written to screen,
indicating the optimal subset(s).

Consider the following instance of the knapsack problem with capacity W = 6 Item Weight Value 3 $25 $20 $15 $40 $50

b) For the bottom-up dynamic programming algorithm, prove that its time efficiency is in
Θ(nW), its space efficiency is in Θ(nW) and the time needed to find the composition of an
optimal subset from a filled dynamic programming table is in O(n).

Answer 1

#open the file in read mode
f = open("data.txt", "r")
#read the first line which has headings
line = f.readline()
#create empty lists for weights and values
weights = []
values = []
#it is used to store the total number of items
length = 0
#read the first line
line = f.readline()
while(line):
   print(line)
   temp = line.split(",")
   #for each line split the data and add the values of weights and values in the corresponding lists
   weights.append(int(temp[1]))
   values.append(int(temp[2]))
   #increment length
   length += 1
   #read the next line
   line = f.readline()
print(weights)
print(values)
print(length)
#knapsack program using bottom up dynamic programming approach
def knapsack_bottonup(weight:int, weights:list, values:list, length:int):
   #create a matrix with number of rows as the number of items(length) given and the number of columns as the weight given
   dp = [[0 for i in range(weight + 1)] for j in range(length + 1)]
   for item in range(length + 1):
       for w in range(weight + 1):
           #for each item if item is 0 or weight is 0 the element in dp will be 0
           if(item == 0 or w == 0):
               dp[item][w] = 0
           #for each item if weight of item is less than the given weight take the maximum with including the weight and without including the weight
           elif(weights[item - 1] <= w):
               dp[item][w] = max(values[item - 1] + dp[item - 1][w - weights[item - 1]], dp[item - 1][w])
           #if the weight of item is less than the given weight then take the previous element in dp matrix
           else:
               dp[item][w] = dp[item - 1][w]
   #take the last element from dp which contains the optimal value
   return dp[length][weight]
print(knapsack_bottonup(6, weights, values, length))

Fri 03:10 Activities Text Editor Open & knapsack.py /Desktop Save = 0 * *Untitled Document data.txt knapsack.py *Untitled Document 1 #open the file in read mode f = open("data.txt", "r") #read the first line which has headings line = f.readline() #create empty lists for weights and values weights = [] values = [] #it is used to store the total number of items length = 0 #read the first line line = f.readline() while(line): print(line) temp = line.split(",) #for each line split the data and add the values of weights and values in the corresponding lists weights.append(int(temp[1])) values.append(int(temp[2])) #increment length length += 1 #read the next line line = f.readline() print(weights) print(values) print(length) #knapsack program using bottom up dynamic programming approach def knapsack_bottonup(weight:int, weights:list, values:list, length:int): #create a matrix with number of rows as the number of items (length) given and the number of columns as the weight given dp = [[O for i in range(weight + 1)] for j in range(length + 1)] for item in range(length + 1): for win range(weight + 1): #for each item if item is oor weight is the element in dp will be o if(item == or W == 0): dp[item][w] = 0 #for each item if weight of item is less than the given weight take the maximum with including the weight and without including the weight -liftuninhteritom 11 -- w . Python Tab Width: 8 Ln 27, Col 110 INS

Activities Text Editor Fri 03:10 Open A knapsack.py /Desktop Save data.txt knapsack.py *Untitled Document 1 cune = 1.Teadline while(line): print(line) temp = line.split("") #for each line split the data and add the values of weights and values in the corresponding lists weights.append(int(temp[1])) values.append(int(temp[2])) #increment length length += 1 #read the next line line = f.readline() print(weights) print(values) print(length) #knapsack program using bottom up dynamic programming approach def knapsack_bottonup(weight:int, weights:list, values:list, length:int): #create a matrix with number of rows as the number of items (length) given and the number of columns as the weight given dp = [[O for i in range(weight + 1)] for j in range(length + 1)] for item in range(length + 1): for win range(weight + 1): #for each item if item is oor weight is the element in dp will be o if(item == or W == 0): dp[item][w] = 0 #for each item if weight of item is less than the given weight take the maximum with including the weight and without including the weight elif(weights[item - 1] <= w): dp[item][w] = max(values[item - 1] + dp[item - 1][w - weights[item - 1]], dp[item - 1][w]) #if the weight of item is less than the given weight then take the previous element in dp matrix else: dp[item][w] = dp[item - 1][w] #take the last element from dp which contains the optimal value return dp[length][weight] print(knapsack_bottonup(6, weights, values, length)) Python Tab Width: 8 Ln 27, Col 110 INS

Activities Terminal Fri 03:10 deepika@deepika-TravelMate-P243-M: -/Desktop File Edit View Search Terminal Help deepika@deepika-TravelMate-P243-M:-/Desktop$ python3 knapsack.py 1,3,25 File Edit View ka-Travel opika@deciew Search 2,2,20 3,1,15 4,4,40 5,5,50 [3, 2, 1, 4, 5] [25, 20, 15, 40, 50] deepika@deepika-TravelMate-P243-M:~/Desktops I

Activities Text Editor Fri 03:13 Open A data.txt -Desktop Save data.txt data.txt x knapsack.py *Untitled Document 1 item, weight, value 1,3,25 2,2,20 3,1,15 4,4,40 5,5,50 Plain Text Tab Width: 8 Ln 2, Col7 INS

time complexity and space complexity:
Time Complexity:
consider the number of items as n
let the weight given be W
Consider the program
The outer loop runs till the item value reaches n (which runs for n + 1 times 0 to n)
The inner loop runs till the weight values reaches W(which runs for W + 1 times 0 to W)
so the time complexity will be O((n + 1)(W + 1)) which gives O(nW)

Space Complexity:
To use the property of memoization in dynamic programming
A matrix is used to store the values of problems and using it whenever same problem is repeated
so the space allocated for the matrix will be the extra space
consider the matrix dimensions
which contains the number of rows as given Weight(W + 1) and number of columns as number of item(n + 1)
so the space complexity will be O((W + 1)(n + 1)) gives O(nW)

Time needed to get optimal solution from the table
To find the total value of the items in the optimal subset it will take o(1) (just access the element from table)
To find the subset which gives that value it will take O(n) since the table has to be traversed using the values

If you have any doubts please comment and please don't dislike.