# 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
```