Greedy algorithm for a knapsack problem with the example of Robbery in Python

Here, we will learn to use greedy algorithm for a knapsack problem with the example of Robbery using Python program.
Submitted by Anuj Singh, on May 12, 2020

Unfortunately, a thief targeted a house and there he found lots of items to steal. Now each item has its value (quantified) and volume. Now the thief has to decide which item to take so that he can have maximum value within a constrained volume. This is an optimization problem in which we have to optimize the overall quantified value by selecting the best items to steal within his bag. The bag can have a maximum volume of 54 Liters.

Program:

# Greedy Algorithm for a Robbery

# Defined a class for items, with 
# its name, value and volume 
# We have to optimise the selection 
# with maximum value within 1000 unit volume space
class itmcls(object):
    def __init__(self, name, val, vol):
        self.name = name
        self.val = val
        self.vol = vol
        
    def getvalue(self):
        return self.val
    
    def getvol(self):
        return self.vol
    
    def density(self):
        return (self.val)/(self.vol)
    
    def __str__(self):
        return self.name 
  
# Defining a function for building a bag 
# which generates list of itmcls    
def buildbag(names, values, volumes):
    bag = []
    for i in range(len(names)):
        bag.append(itmcls(names[i], values[i], volumes[i]))
    return bag

# Implementation of greedy algorithm to choose 
# one of the optimum choice
def greedy(items, maxvol, keyfunction):
    itemscopy = sorted(items, key = keyfunction, reverse = True)
    
    result = []
    totalval = 0 
    totalvol = 0
    
    for i in range(len(items)):
        if (totalvol + itemscopy[i].getvol() <= maxvol):
            result.append(itemscopy[i])
            totalval = totalval + itemscopy[i].getvalue()
            totalvol = totalvol + itemscopy[i].getvol()
            
    return (result, totalval)

# Main Function
itemlist = ['phone', 'laptop', 'applemacbook', 'ipad', 'Money', 'goldcoin', 'coldrink', 'bowl']
values = [89,90,95,78,97,84,32,45]
volumes = [6,8,15,17,12,18,8,9]
itemlistt = buildbag(itemlist, values, volumes)
maxvol = 54

taken, totvalue = greedy(itemlistt, maxvol, itmcls.density)

print('Total vaule taken : ', totvalue)

# Printing the list of items slected for 
# optimum value in terms of density
for i in range(len(taken)):
    print('  ', taken[i])

Output

Total vaule taken :  416
   phone
   laptop
   Money
   applemacbook
   bowl