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.


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


Total vaule taken :  416

Comments and Discussions!

Load comments ↻

Copyright © 2024 All rights reserved.