Q:

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

belongs to collection: Python miscellaneous programs

mahmoud2506
Save to bookmark
|
2022-05-25
|
  397 
0

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.

Python programming, examples, Python programming examples,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-25
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Python miscellaneous programs
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Corona Virus Live Updates for India (District Wise... >>
<< Python program to generate the QR code in Python...