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
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])
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started