Problem: MULTIPLE KNAPSACK: Given n objects, each with a value vi and a weight w

Question

Problem: MULTIPLE KNAPSACK: Given n objects, each with a value vi and a weight wi, and k knapsacks, each with capacity C, assign objects to the knapsacks so that the total weight of the objects in each does not exceed C and the total value of all the selected objects is maximized.
and make the program have capacity that can be changed for each individual knapsack.
I already have a small code of this in python those it's missing the ability to have capacity be entered in for each individual knapsack could someone please help me fix the code. I'm a notice at python and I don't know how I should go about giving this program the ability to enter in different capacity for each individual knapsacks the code is as follows:
# Take input from user
n = int(input('How many objects (enter the value of n): '))
k = int(input('How many knapsacks (enter the value of k): '))
c = int(input('What is capacity of each knapsack (enter the value of c): '))
v=[]
w=[]
indx=[]
valuePerUnitWt = []
for i in range(0,n):
v.append(int(input('Enter value of object '+str(i+1)+' (v'+str(i+1)+'):')))
w.append(int(input('Enter weight of object '+str(i+1)+' (w'+str(i+1)+'):')))
valuePerUnitWt.append(v[i]/w[i])
indx.append(i+1)
#create k empty knapsacks
knapsacks=[]
knapsacksCapacityLeft=[]
for i in range(0,k):
knapsacks.append([])
knapsacksCapacityLeft.append(c)
# Apply Greedy strategy until you have an item that can fit in some knapsack
while(True):
if(len(valuePerUnitWt)==0): #if you do not have any item left to be put in knapsack then quit
break;
mostValuableItemIndex = valuePerUnitWt.index(max(valuePerUnitWt)) # Find the most-valuable-item
#Check if you have a knapsack that can accomodate this most-valuable-item
for i in range(0,k):
if (knapsacksCapacityLeft[i]>=w[mostValuableItemIndex]): #found
knapsacksCapacityLeft[i] = knapsacksCapacityLeft[i] - w[mostValuableItemIndex] #reduce the capacity
knapsacks[i].append(indx[mostValuableItemIndex]) #and add that item in the knapsack list
break;
# delete the most-valuable-item from available items
del v[mostValuableItemIndex]
del w[mostValuableItemIndex]
del valuePerUnitWt[mostValuableItemIndex]
del indx[mostValuableItemIndex]

#print the assignment
for i in range(0,k):
print('Objects in knapsack '+str(i)+' are:')
print(knapsacks[i])

Explanation / Answer

Made a little modification and it's working if you have any confusion or question ask in comment ready to help. # Take input from user n = int(input('How many objects (enter the value of n): ')) k = int(input('How many knapsacks (enter the value of k): ')) knapsacks = [[] for _ in range(k)] knapsacksCapacityLeft = [] #0'th index will have capacity of first knapsack and so on for i in range(k): c = int(input('What is capacity of %d knapsack (enter the value of c): ' % i)) knapsacksCapacityLeft.append(c) v=[] w=[] indx=[] valuePerUnitWt = [] for i in range(0,n): v.append(int(input('Enter value of object '+str(i+1)+' (v'+str(i+1)+'):'))) w.append(int(input('Enter weight of object '+str(i+1)+' (w'+str(i+1)+'):'))) valuePerUnitWt.append(v[i]/w[i]) indx.append(i+1) # Apply Greedy strategy until you have an item that can fit in some knapsack while(True): if(len(valuePerUnitWt)==0): #if you do not have any item left to be put in knapsack then quit break; mostValuableItemIndex = valuePerUnitWt.index(max(valuePerUnitWt)) # Find the most-valuable-item #Check if you have a knapsack that can accomodate this most-valuable-item for i in range(k): if (knapsacksCapacityLeft[i]>=w[mostValuableItemIndex]): #found knapsacksCapacityLeft[i] = knapsacksCapacityLeft[i] - w[mostValuableItemIndex] #reduce the capacity knapsacks[i].append(indx[mostValuableItemIndex]) #and add that item in the knapsack list break; # delete the most-valuable-item from available items del v[mostValuableItemIndex] del w[mostValuableItemIndex] del valuePerUnitWt[mostValuableItemIndex] del indx[mostValuableItemIndex] #print the assignment for i in range(0,k): print('Objects in knapsack '+str(i)+' are:') print(knapsacks[i])

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.