Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Faça uso do algoritmo em python para resolver o problema de Knapsack

0 votos
22 visitas
perguntada Nov 2 em Matemática por Fábio Springer (11 pontos)  
editado Nov 6 por Fábio Springer

Faça uso do algoritmo em python para resolver o problema de Knapsack para os seguintes grupos: (a) Profits 122 2 144 133 52 172 169 50 11 87 127 31 10 132 59
Weights 63 1 71 73 24 79 82 23 6 43 66 17 5 65 29
Capacity 323
(b) Profits 143 440 120 146 266 574 386 512 106 418 376 124 48 535 55
Weights 72 202 56 73 144 277 182 240 54 192 183 67 23 244 29
Capacity 1019
(c) Profits 818 460 267 75 621 280 555 214 721 427 78 754 704 44 371
Weights 380 213 138 35 321 138 280 118 361 223 37 389 387 23 191
Capacity 1617

Exercício baseado em no exercício 4.4 do livro Combinatorial Algorithms: Generation, Enumeration and Search.

Compartilhe

1 Resposta

0 votos
respondida Nov 2 por Fábio Springer (11 pontos)  

Problemas do tipo Knapsack consistem em dado um conjunto de items otimizar a quantidade de itens levados de forma que não se ultrapasse um determinado peso. Nesse caso dado a capacidade C em unidades, o preço PR e o peso WT queremos retornar o maior valor em reais que podemos levar dentro da nossa mochila. Dito isso vamos ao problema:

def knapSack(C, wt, pr, n):
   K = [[0 for x in range(C + 1)] for x in range(n + 1)]
   # bottom up
   for i in range(n + 1):
      for C in range(C + 1):
         if i == 0 or C == 0:
            K[i][C] = 0
         elif wt[i-1] <= C:
            K[i][C] = max(pr[i-1] + K[i-1][C-wt[i-1]], K[i-1][C])
         else:
            K[i][C] = K[i-1][C]
   return K[n][C]

definimos a nossa função, agora basta colocar os valores dos três items propostos:

if __name__ == "__main__":
    # A)
    pr_A = [122, 2, 144, 133, 52, 172, 16, 50, 11, 87, 127, 31, 10, 132, 59]
    wt_A = [63, 1, 71, 73,24, 79, 82, 23, 6, 43, 66, 17, 5, 65, 29]
    C_A = 323
    n_A = len(pr_A)
    # B)
    pr_B = [143, 440, 120, 146, 266, 574, 386, 512, 106, 418, 376, 124, 48, 535, 55]
    wt_B = [7,2, 202, 56, 73, 144, 277, 182, 240, 54, 192, 183, 67, 23, 244, 29]
    C_B = 1019
    n_B = len(pr_B)
    # C) 
    pr_C = [818, 460, 267, 75, 621, 280, 555, 214, 721, 427, 78, 754, 704, 44, 371]
    wt_C = [ 380, 213, 138, 35,321, 138, 280, 118, 361, 223, 37, 389, 387, 23, 191]
    C_C = 1617
    n_C = len(pr_C)
    print( "A =", knapSack(C_A, wt_A, pr_A, n_A), "B = ", knapSack(C_B, wt_B, pr_B, n_B), "C = ", knapSack(C_C, wt_C, pr_C, n_C))

E temos o seguinte resultado:
A = 670 B = 3796 C = 3298

comentou Nov 6 por Pedro Watuhã (1 ponto)  
Boa Noite, gostei muito da resolução apresentada e acredito que essa seja a abordagem mais didática e que apresenta resultados de forma mais eficiente. Todavia, acho que possa ser interessante explicitar um pouco mais do step-by-step utilizado por esse método de programação dinâmica e trazer outras abordagens como uma de força bruta e de métodos gananciosos. Obtive alguns algoritmos já implementados dessas abordagens no Python Pool, https://www.pythonpool.com/knapsack-problem-python/#:~:text=Conclusion-,What%20is%20Knapsack%20Problem%20in%20Python%3F,specific%20weight%20and%20a%20value, e os testei, obtendo os mesmos resultados que o algoritmo dinâmico. Mesmo assim, acredito que o trabalho esteja muito bom.
...