neste tutorial anterior discutimos Fracionário da Mochila problema utilizando a abordagem Gananciosa. Nós mostramos que a abordagem gananciosa dá uma solução ideal para a mochila fraccionada. No entanto, este capítulo cobrirá o problema da mochila 0-1 e a sua análise.
In 0-1 Knapsack, items cannot be broken which means the thief should take the item as a whole or should leave it., Esta é a razão por trás de chamá-lo de Mochila 0-1.
portanto, no caso de uma mochila 0-1, o valor de xi pode ser 0 ou 1, onde outras restrições permanecem as mesmas.
0-1 A mochila não pode ser resolvida por uma abordagem gananciosa. Abordagem gananciosa não garante uma solução ideal. Em muitos casos, abordagem gananciosa pode dar uma solução ideal.
os seguintes exemplos estabelecerão a nossa Declaração.
exemplo-1
vamos considerar que a capacidade da mochila é W = 25 e os itens são como mostrado na tabela seguinte.,
| Item | A | B | C | D |
|---|---|---|---|---|
| Lucro | 24 | 18 | 18 | 10 |
| Peso | 24 | 10 | 10 | 7 |
Sem considerar o lucro por unidade de peso (pi/wi), se aplicarmos Gananciosos abordagem para solucionar este problema, o primeiro item será selecionado como ele irá contribuir o máximo de lucro entre todos os elementos.,
Depois de seleccionar o item a, não será seleccionado mais nenhum item. Por conseguinte, para este conjunto de rubricas, o lucro total é de 24. Considerando que a solução ideal pode ser alcançada selecionando itens, B E C, onde o lucro total é 18 + 18 = 36.
Exemplo-2
em vez de seleccionar os itens com base no benefício global, neste exemplo, os itens são seleccionados com base na relação pi/wi. Consideremos que a capacidade da mochila é W = 60 e os itens são como mostrado na tabela seguinte.,
| Item | A | B | C |
|---|---|---|---|
| Price | 100 | 280 | 120 |
| Weight | 10 | 40 | 20 |
| Ratio | 10 | 7 | 6 |
Using the Greedy approach, first item A is selected. Then, the next item B is chosen. Hence, the total profit is 100 + 280 = 380., No entanto, a solução ideal desta instância pode ser alcançada selecionando itens, B E C, onde o lucro total é 280 + 120 = 400.por conseguinte, pode concluir-se que a abordagem gananciosa pode não dar uma solução óptima.
para resolver o Knapsack 0-1, é necessária uma abordagem dinâmica de programação.
Declaração de problema
um ladrão está roubando uma loja e pode carregar um peso máximo de W em sua mochila. Há n itens e peso do ith item é wi e o lucro de selecionar este item é pi. Que itens deve o ladrão levar?,
abordagem dinâmica de programação
Let I be the highest-numered item in an optimal solution s for W dollars. Então S ‘ = S – {I} é uma solução ideal para W-wi dólares e o valor para a solução S é Vi mais o valor do sub-problema.
podemos expressar este fato na seguinte fórmula: defina c para ser a solução para os itens 1,2, … , i e o peso máximo W.,
O algoritmo tem os seguintes entradas
-
O máximo de peso W
-
O número de itens n
-
As duas sequências v = <v1, v2, …, vn> e w = <w1, w2, …, wn>
O conjunto de itens para levar pode ser deduzida a partir da tabela, começando em c e o rastreio para trás, onde os valores ideais veio.
análise
este algoritmo toma θ(n, w) vezes como a tabela c tem (n + 1).(w + 1) entradas, onde cada entrada requer θ (1) tempo para calcular.,