No código abaixo, a solução do problema será encontrada usando uma tabela \(V[0,\cdots,n,0,\cdots,W\). Cada posição \(V[i,x]\) da tabela irá guardar a máximo valor da mochila que pode ser conseguida usando os ítens \(\{1,2,\cdots,i\}\) e uma mochila com tamanho máximo \(x\). linha \(n\) da tabela irá guardar os máximos valores da mochila para uma mochila com capacidade máxima \(x\). Para encontrar os valores máximos, a construção da mochila considera duas possibilidades: incluir o ítem \(i\) (quando possível e dependendo da capacidade \(x\)) e não inclui-lo.
import numpy as np
def solve_Knapsack_DP(weights,values,capacity):
n=len(weights)
valueFunction=np.zeros([n+1,capacity+1])
contentMatrix=np.zeros([n+1,capacity+1])
for i in range(1,n+1): # The item 0 considers the empty knapsack
for x in range(0,capacity+1):
if(x-weights[i-1]>=0):
valueFunction[i,x]=max(valueFunction[i-1,x],valueFunction[i-1,x-weights[i-1]]+values[i-1])
if(valueFunction[i-1,x]<valueFunction[i-1,x-weights[i-1]]+values[i-1]):
contentMatrix[i,x]=1
else:
valueFunction[i,x]=valueFunction[i-1,x]
return valueFunction,contentMatrix
def disclosure_content(contentMatrix,weights):
[n,capacity]=np.shape(contentMatrix)
n=n-1
capacity=capacity-1
content=[]
k=capacity
for i in range(n,0,-1):
if(contentMatrix[i,k]==1):
content.append(i-1)
k=capacity-weights[i-1]
return content
if __name__ == '__main__':
capacity=10
weightList=[]
weightList.append(4)
weightList.append(7)
weightList.append(5)
weightList.append(3)
#weightList.append(25)
valueList=[]
valueList.append(40)
valueList.append(42)
valueList.append(25)
valueList.append(12)
[valueFunction,contentMatrix]= solve_Knapsack_DP(weightList,valueList,capacity)
print valueFunction
print contentMatrix
print disclosure_content(contentMatrix,weightList)
#Output
[[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 40. 40. 40. 40. 40. 40. 40.]
[ 0. 0. 0. 0. 40. 40. 40. 42. 42. 42. 42.]
[ 0. 0. 0. 0. 40. 40. 40. 42. 42. 65. 65.]
[ 0. 0. 0. 12. 40. 40. 40. 52. 52. 65. 65.]]
[[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 1.]
[ 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1.]
[ 0. 0. 0. 1. 0. 0. 0. 1. 1. 0. 0.]]
[2, 0]