algoritmo codicioso para un problema de la mochila con el ejemplo de Robo en Python

Aquí, vamos a aprender a utilizar algoritmo voraz class un problema de la mochila con el ejemplo de robo mediante el programa de Python .

Por desgracia, un ladrón como objetivo una casa y allí encontró un montón de artículos para robar. Ahora, cada elemento tiene su valor (cuantificada) y el volumen. Ahora el ladrón tiene que decidir qué elemento a tomar para que pueda tener un valor máximo dentro de un volumen restringido. Se trata de un problema de optimización en el que tenemos que optimizar el valor global cuantificado mediante la selección de los mejores artículos para robar dentro de su bolsa. La bolsa puede tener un volumen máximo de 54 litros.

Programa:

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

salida

Total vaule taken :  416
phone
laptop
Money
applemacbook
bowl


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *