Question

Como resolver o problema da mochila usando Programação Dinâmica?

Answer 1

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]