En este tutorial, anteriormente hemos hablado de fracciones de Mochila problema utilizando Codiciosos enfoque. Hemos demostrado que el enfoque codicioso da una solución óptima para la mochila fraccionada. Sin embargo, este capítulo cubrirá 0-1 problema mochila y su análisis.
en la mochila 0-1, los artículos no se pueden romper, lo que significa que el ladrón debe tomar el artículo como un todo o debe dejarlo., Esta es la razón detrás de llamarlo como 0-1 Mochila.
Por lo tanto, en el caso de 0-1 Mochila, el valor de xi puede ser 0 o 1, donde otras restricciones siguen siendo las mismas.
0-1 mochila no se puede resolver por enfoque codicioso. El enfoque codicioso no garantiza una solución óptima. En muchos casos, el enfoque codicioso puede dar una solución óptima.
los siguientes ejemplos establecerán nuestra Declaración.
ejemplo-1
consideremos que la capacidad de la mochila es W = 25 y los elementos son como se muestra en la siguiente tabla.,
| Elemento | Un | B | C | D |
|---|---|---|---|---|
| Beneficios | 24 | 18 | 18 | 10 |
| Peso | 24 | 10 | 10 | 7 |
Sin tener en cuenta el beneficio por unidad de peso (pi/wi), si aplicamos Codiciosos enfoque para resolver este problema, el primer elemento de Una será seleccionada como contribuirá máximo beneficio entre todos los elementos.,
después de seleccionar el elemento A, no se seleccionará más elemento. Por lo tanto, para este conjunto dado de artículos el beneficio total es 24. Considerando que, la solución óptima se puede lograr mediante la selección de elementos, B y C, donde el beneficio total es 18 + 18 = 36.
Ejemplo-2
en lugar de seleccionar los elementos en función del beneficio general, en este ejemplo los elementos se seleccionan en función de la relación pi/wi. Consideremos que la capacidad de la mochila es W = 60 y los artículos son como se muestra en la siguiente tabla.,
| 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., Sin embargo, la solución óptima de esta instancia se puede lograr seleccionando elementos, B y C, donde el beneficio total es 280 + 120 = 400.
Por lo tanto, se puede concluir que el enfoque codicioso puede no dar una solución óptima.
para resolver la mochila 0-1, se requiere un enfoque de programación dinámico.
declaración del problema
un ladrón está robando una tienda y puede llevar un peso máximo de W en su mochila. Hay n artículos y el peso del ith artículo es wi y el beneficio de seleccionar este artículo es pi. ¿Qué artículos debe tomar el ladrón?,
enfoque de programación dinámica
deje que yo sea el elemento más numerado en una solución óptima S Para W dólares. Entonces S ‘ = s – {i} es una solución óptima para W-wi dólares y el valor de la solución S es Vi más el valor del subproblema.
podemos expresar este hecho en la siguiente fórmula: define c como la solución para los ítems 1,2,…, i y el peso máximo w.,
El algoritmo tiene las siguientes entradas
-
El peso máximo W
-
El número de elementos n
-
Las dos secuencias v = <v1, v2, …, vn> y w = <w1, w2, …, wn>
El conjunto de elementos a tomar puede ser deducido de la tabla, a partir de c y el rastreo hacia atrás, donde los valores óptimos vino.
análisis
Este algoritmo toma θ(n, w) veces como la tabla c tiene (n + 1).(w + 1) entradas, donde cada entrada requiere θ (1) tiempo para calcular.,