Mochila_PD.py

Mochila_PD.py

def mochila(n, capacidade, peso, valor):

	pd = [[0 for i in range(capacidade+1)] for x in range(n+1)]

	for i in range(1,n+1):
		for j in range(0,capacidade+1):
			if peso[i-1] > j:
				pd[i][j] = pd[i-1][j]
			else:
				pd[i][j] = max(pd[i-1][j], (pd[i-1][j-peso[i-1]] + valor[i-1]))

	lucroMaximo = pd[n][capacidade]

	return lucroMaximo, pd

def recuperaCaminho(pd, lucroMaximo, n, capacidade, peso):
	i = n
	j = capacidade
	val = lucroMaximo

	while(pd[i][j] != 0):
		i -= 1
		if val != pd[i][j]:
			print("Obj:",i+1)
			j -= peso[i]
			val = pd[i][j]

def main():

	capacidade = 7
	peso = [5,8,3,4,1]
	valor = [15,9,20,10,17]
	n = len(peso)

	lucroMaximo, pd= mochila(n, capacidade, peso, valor)

	print('Lucro maximo:',lucroMaximo)

	recuperaCaminho(pd, lucroMaximo, n, capacidade, peso)

	#print(pd)

if __name__ =='__main__':
	main()