in

0-1 Problema de la mochila | DP-10

gfg 200x200 min

Dados los pesos y valores de n artículos, coloque estos artículos en una mochila de capacidad W para obtener el valor total máximo en la mochila. En otras palabras, dadas dos matrices de enteros val[0..n-1] y peso[0..n-1] que representan valores y pesos asociados con n elementos respectivamente. También dado un entero W que representa la capacidad de la mochila, averigüe el subconjunto de valor máximo de val[] de modo que la suma de los pesos de este subconjunto sea menor o igual que W. No puede romper un artículo, ya sea que elija el artículo completo o no lo elija (propiedad 0-1).

problema de la mochila

Método 1: Recurrencia por algoritmo de fuerza bruta O búsqueda exhaustiva.
Acercarse: Una solución simple es considerar todos los subconjuntos de elementos y calcular el peso y el valor total de todos los subconjuntos. Considere los únicos subconjuntos cuyo peso total es menor que W. De todos esos subconjuntos, elija el subconjunto de valor máximo.
Subestructura óptima: Para considerar todos los subconjuntos de elementos, puede haber dos casos para cada elemento.

  1. Caso 1: El artículo está incluido en el subconjunto óptimo.
  2. Caso 2: El artículo no está incluido en el conjunto óptimo.

Por lo tanto, el valor máximo que se puede obtener de ‘n’ elementos es el máximo de los dos valores siguientes.

  1. Valor máximo obtenido por n-1 artículos y peso W (excluyendo artículo n).
  2. Valor del n-ésimo elemento más el valor máximo obtenido por n-1 elementos y W menos el peso del n-ésimo elemento (incluido el n-ésimo elemento).

Si el peso del ‘n-ésimo’ artículo es mayor que ‘W’, entonces el n-ésimo elemento no se puede incluir y Caso 1 es la única posibilidad.

A continuación se muestra la implementación del enfoque anterior:

C ++

 

#include <bits/stdc++.h>

using namespace std;

int max(int a, int b) { return (a > b) ? a : b; }

int knapSack(int W, int wt[], int val[], int n)

{

    

    if (n == 0 || W == 0)

        return 0;

    

    

    

    

    if (wt[n - 1] > W)

        return knapSack(W, wt, val, n - 1);

    

    

    

    else

        return max(

            val[n - 1]

                + knapSack(W - wt[n - 1],

                           wt, val, n - 1),

            knapSack(W, wt, val, n - 1));

}

int main()

{

    int val[] = { 60, 100, 120 };

    int wt[] = { 10, 20, 30 };

    int W = 50;

    int n = sizeof(val) / sizeof(val[0]);

    cout << knapSack(W, wt, val, n);

    return 0;

}

C

#include <stdio.h>

int max(int a, int b) { return (a > b) ? a : b; }

int knapSack(int W, int wt[], int val[], int n)

{

    

    if (n == 0 || W == 0)

        return 0;

    

    

    

    if (wt[n - 1] > W)

        return knapSack(W, wt, val, n - 1);

    

    

    

    else

        return max(

            val[n - 1]

                + knapSack(W - wt[n - 1],

                           wt, val, n - 1),

            knapSack(W, wt, val, n - 1));

}

int main()

{

    int val[] = { 60, 100, 120 };

    int wt[] = { 10, 20, 30 };

    int W = 50;

    int n = sizeof(val) / sizeof(val[0]);

    printf("%d", knapSack(W, wt, val, n));

    return 0;

}

Java

class Knapsack {

    

    

    static int max(int a, int b)

    {

      return (a > b) ? a : b;

    }

    

    

    

    static int knapSack(int W, int wt[], int val[], int n)

    {

        

        if (n == 0 || W == 0)

            return 0;

        

        

        

        

        if (peso[n - 1] > W)

            return knapSack(W, wt, val, n - 1);

        

        

        

        else

            return max (val[n - 1]

                       + knapSack (W - peso[n - 1], peso,

                                  val, n - 1),

                       knapSack(W, wt, val, n - 1));

    }

    

    public static void main(String args[])

    {

        int val[] = new int[] { 60, 100, 120 };

        int wt[] = new int[] { 10, 20, 30 };

        int W = 50;

        int n = val.length;

        System.out.println(knapSack(W, wt, val, n));

    }

}

Pitón

def knapSack(W, wt, val, n):

    

    if n == 0 or W == 0:

        return 0

    

    

    

    

    if (peso[n-1] > W):

        return knapSack(W, wt, val, n-1)

    

    

    

    else:

        return max(

            val[n-1] + knapSack(

                W-peso[n-1], peso, val, n-1),

            knapSack(W, wt, val, n-1))

val = [60, 100, 120]

wt = [10, 20, 30]

W = 50

n = len(val)

print knapSack(W, wt, val, n)

C#

using System;

class GFG {

    

    

    static int max(int a, int b)

    {

         return (a > b) ? a : b;

    }

    

    

    static int knapSack(int W, int[] wt,

                        int[] val, int n)

    {

        

        if (n == 0 || W == 0)

            return 0;

        

        

        

        

        if (wt[n - 1] > W)

            return knapSack(W, wt,

                            val, n - 1);

        

        

        

        else

            return max(val[n - 1]

                       + knapSack(W - wt[n - 1], wt,

                                  val, n - 1),

                       knapSack(W, wt, val, n - 1));

    }

    

    public static void Main()

    {

        int[] val = new int[] { 60, 100, 120 };

        int[] wt = new int[] { 10, 20, 30 };

        int W = 50;

        int n = val.Length;

        Console.WriteLine(knapSack(W, wt, val, n));

    }

}

PHP

<?php

function knapSack($W, $wt, $val, $n)

{

    

    if ($n == 0 || $W == 0)

        return 0;

    

    

    

    

    

    if ($wt[$n - 1] > $W)

        return knapSack($W, $wt, $val, $n - 1);

    

    

    

    

    else

        return max($val[$n - 1] +

               knapSack($W - $wt[$n - 1],

               $wt, $val, $n - 1),

               knapSack($W, $wt, $val, $n-1));

}

    

    $val = array(60, 100, 120);

    $wt = array(10, 20, 30);

    $W = 50;

    $n = count($val);

    echo knapSack($W, $wt, $val, $n);

?>

Javascript

<script>

    

    

    

    

    

    function max(a, b)

    {

         return (a > b) ? a : b;

    }

 

    

    

    function knapSack(W, wt, val, n)

    {

 

        

        if (n == 0 || W == 0)

            return 0;

 

        

        

        

        

        if (wt[n - 1] > W)

            return knapSack(W, wt, val, n - 1);

 

        

        

        

        else

            return max(val[n - 1] +

            knapSack(W - wt[n - 1], wt, val, n - 1),

            knapSack(W, wt, val, n - 1));

    }

      

    let val = [ 60, 100, 120 ];

    let wt = [ 10, 20, 30 ];

       let W = 50;

    let n = val.length;

    document.write(knapSack(W, wt, val, n));

    

</script>

Cabe señalar que la función anterior calcula los mismos subproblemas una y otra vez. Consulte el siguiente árbol de recursividad, K (1, 1) se está evaluando dos veces. La complejidad temporal de esta ingenua solución recursiva es exponencial (2 ^ n).

In the following recursion tree, K() refers 
to knapSack(). The two parameters indicated in the
following recursion tree are n and W.
The recursion tree is for following sample inputs.
wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30}
                       K(n, W)
                       K(3, 2)  
                   /             
                 /                               
            K(2, 2)                  K(2, 1)
          /                         /     
        /                         /        
       K(1, 2)      K(1, 1)        K(1, 1)     K(1, 0)
       /           /                 /        
     /           /                 /            
K(0, 2)  K(0, 1)  K(0, 1)  K(0, 0)  K(0, 1)   K(0, 0)
Recursion tree for Knapsack capacity 2 
units and 3 items of 1 unit weight.

Análisis de complejidad:

  • Complejidad del tiempo: O (2norte).
    Ya que hay subproblemas redundantes.
  • Espacio auxiliar:O (1).
    Dado que no se ha utilizado ninguna estructura de datos adicional para almacenar valores.

Dado que los subproblemas se evalúan nuevamente, este problema tiene la propiedad Subproblemas superpuestos. Entonces, el problema de la mochila 0-1 tiene ambas propiedades (ver esto y esto) de un problema de programación dinámica.

Método 2: Al igual que otros problemas típicos de programación dinámica (DP), se puede evitar el recálculo de los mismos subproblemas construyendo una matriz temporal K[][] de forma ascendente. A continuación se muestra la implementación basada en programación dinámica.

Acercarse: En la programación dinámica trabajaremos considerando los mismos casos mencionados en el enfoque recursivo. En un DP[][] En la tabla, consideremos todos los pesos posibles de ‘1’ a ‘W’ como las columnas y los pesos que se pueden mantener como filas.
El estado DP[i][j] denotará el valor máximo de ‘peso-j’ considerando todos los valores de ‘1 a iésimo’. Entonces, si consideramos ‘wi’ (peso en la fila ‘i-ésima’), podemos completarlo en todas las columnas que tienen ‘valores de peso> wi’. Ahora pueden darse dos posibilidades:

  • Complete ‘wi’ en la columna dada.
  • No llene ‘wi’ en la columna dada.

Ahora tenemos que tomar un máximo de estas dos posibilidades, formalmente si no llenamos el peso ‘i-ésimo’ en la columna ‘j-ésima’, entonces DP[i][j] el estado será el mismo que DP[i-1][j] pero si llenamos el peso, DP[i][j] será igual al valor de ‘wi’ + valor de la columna que pesa ‘j-wi’ en la fila anterior. Así que aprovechamos el máximo de estas dos posibilidades para llenar el estado actual. Esta visualización aclarará el concepto:

Let weight elements = {1, 2, 3}
Let weight values = {10, 15, 40}
Capacity=6

0   1   2   3   4   5   6

0  0   0   0   0   0   0   0

1  0  10  10  10  10  10  10

2  0  10  15  25  25  25  25

3  0
 
Explanation:
For filling 'weight = 2' we come 
across 'j = 3' in which 
we take maximum of 
(10, 15 + DP[1][3-2]) = 25   
  |        |
'2'       '2 filled'
not filled  

0   1   2   3   4   5   6

0  0   0   0   0   0   0   0

1  0  10  10  10  10  10  10

2  0  10  15  25  25  25  25

3  0  10  15  40  50  55  65

Explanation:
For filling 'weight=3', 
we come across 'j=4' in which 
we take maximum of (25, 40 + DP[2][4-3]) 
= 50

For filling 'weight=3' 
we come across 'j=5' in which 
we take maximum of (25, 40 + DP[2][5-3])
= 55

For filling 'weight=3' 
we come across 'j=6' in which 
we take maximum of (25, 40 + DP[2][6-3])
= 65

C ++

#include <bits/stdc++.h>

using namespace std;

int max(int a, int b)

{

    return (a > b) ? a : b;

}

int knapSack(int W, int wt[], int val[], int n)

{

    int i, w;

      vector<vector<int>> K(n + 1, vector<int>(W + 1));

    

    for(i = 0; i <= n; i++)

    {

        for(w = 0; w <= W; w++)

        {

            if (i == 0 || w == 0)

                K[i][w] = 0;

            else if (wt[i - 1] <= w)

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

apple touch icon@2

Configurar un trabajo cron en Windows

186288

Producto Interno Bruto (PIB) vs Producto Nacional Bruto (PNB) – Diferencia y Comparación