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.
Can anyone give a program in c++, java or python design that implement a simple heursistic to solve this problem, an example of a simple heursist is a greedy aglorthim. An example of a greedy heuristic not in program form is this. S1 = min(cjpi/w+ij) = = pi/max(wij/cj), 1 <= j <= m). would be something like that. Also include the equation form of it as well with a description.

Explanation / Answer

# 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])

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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