KNAPSACK 0/1 MEDIUM
problema
Você tem n itens, cada um com um peso e um valor, e uma mochila que aguenta no máximo
W de peso. Escolha quais itens levar para maximizar o valor total sem passar da capacidade.
É "0/1" porque cada item é levado inteiro ou não é levado: não dá para fracionar nem repetir.
Exemplo · itens (peso, valor) =
(1, 1) (3, 4) (3, 5) (3, 7), W = 7 → 13
Levar os itens de peso 1, 3 (valor 5) e 3 (valor 7): peso 7, valor 1 + 5 + 7 = 13. Levar os três itens de peso 3 daria peso 9, acima da capacidade.