Question

Suppose you are an art thief (not a good start) who has broken into an art gallery. All you have to haul out your stolen art is your briefcase which holds only W pounds of art and for every piece of art, you know its weight. Write a program that contains a dynamic programming function to determine your maximum profit. Include a main program that tests your function against each of the following two data sets (each happens to have n=5 items; but your function should work for other values of n as well; we are likely to test your code against another random dataset with an unknown number of items):

Data set 1:

Items 1, 2, 3, 4, and 5 have weights 2, 3, 4, 5 , 9 and value 3, 4, 8, 8, and 10, respectively. Let W = 20.

Data set 2:

Items 1, 2, 3, 4, and 5 have weights 1, 2, 5, 6, 7 and value 1, 6, 18, 22, and 28, respectively. Let W = 11.

Answer 1

Check the explanation

Step-by-step explanation:

weights = [2,3,4,5,9] #assign the weights here

value = [3,4,8,8,10] #assign the values here

#recursive function to get the maximum weight for a given knapsack

def getMaxWeight(weights,value,W,n):

#check if any elements are there or check if the knapsack can hold any more weights

if(n==0 or W==0):

return 0

elif(weights[n]>W):

#if the current value of the weight is greater than what a knapsack can hold then discard that

return getMaxWeight(weights,value,W,n-1)

else:

#either choose the current weight or do not choose based on the maximum values

return max(value[n]+getMaxWeight(weights,value,W-weights[n],n-1),getMaxWeight(weights,value,W,n-1))

if __name__ == '__main__':

W=20

n=len(weights)-1

print("Weights are:",weights)

print("Values are:",value)

print("Maximum value for given knapsack is:",getMaxWeight(weights,value,W,n))

Kindly check the attached output images below.