/* A Naive recursive implementation of  0-1 Knapsack problem */ #include  using namespace std; // A utility function that returns // maximum of two integers int max(int a, int b) { return (a>b) ? a: b; } // Devuelve el valor máximo que // se puede poner en una mochila de capacidad W int knapSack(int W, int wt[], int val[], int n) // Caso base if (n == 0 // Código de controlador int main() { int beneficio[] = { 60, 100, 120 }; int peso[] = { 10, 20, 30 }; int W = 50; 0]);<< knapSack(W, weight, profit, n);  return 0; } // This code is contributed by rathbhupendra>

/* A Naive recursive implementation of 0-1 Knapsack problem */ #include  // A utility function that returns // maximum of two integers int max(int a, int b) { return (a>b) ? a: b; } // Devuelve el valor máximo que // se puede poner en una mochila de capacidad W int knapSack(int W, int wt[], int val[], int n) W == 0) return 0;  // Si el peso del enésimo artículo es mayor que // la capacidad de la mochila W, entonces este artículo // no puede incluirse en la solución óptima si (wt[n - 1]> W) return knapSack(W, wt, val, n - 1);  // Devuelve el máximo de dos casos: // (1) enésimo elemento incluido // (2) no incluido else return max( val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), mochila(W, wt, val, n - 1));  // Código del controlador int main() { int beneficio[] = { 60, 100, 120 };  int peso[] = {10, 20, 30};  int W = 50;  int n = tamaño de (beneficio) / tamaño de (beneficio [0]);  printf('%d', knapSack(W, peso, beneficio, n));  devolver 0; }>

/* A Naive recursive implementation of 0-1 Knapsack problem */ class Knapsack {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>b) ? a: b; } // Devuelve el valor máximo que // se puede poner en una mochila de // capacidad W static int knapSack(int W, int wt[], int val[], int n) // Código del controlador public static void main( String args[]) { int beneficio[] = nuevo int[] { 60, 100, 120 };  int peso[] = nuevo int[] { 10, 20, 30 };  int W = 50;  int n = beneficio.longitud;  System.out.println(knapSack(W, peso, beneficio, n));  } } /*Este código es aportado por Rajat Mishra */>

# A naive recursive implementation # of 0-1 Knapsack Problem # Returns the maximum value that # can be put in a knapsack of # capacity W def knapSack(W, wt, val, n): # Base Case if n == 0 or W == 0: return 0 # If weight of the nth item is # more than Knapsack of capacity W, # then this item cannot be included # in the optimal solution if (wt[n-1]>W): return knapSack(W, wt, val, n-1) # devuelve el máximo de dos casos: # (1) enésimo artículo incluido # (2) no incluido else: return max( val[n-1] + knapSack ( W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # fin de función knapSack # Código de controlador si __name__ == '__main__': beneficio = [60, 100, 120] peso = [10, 20, 30] W = 50 n = len(beneficio) print knapSack(W, peso, beneficio, n) # Este código es una aportación de Nikhil Kumar Singh>

/* A Naive recursive implementation of 0-1 Knapsack problem */ using System; class GFG {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>b) ? a: b; } // Devuelve el valor máximo que // se puede poner en una mochila de capacidad W static int knapSack(int W, int[] wt, int[] val, int n) W == 0) return 0;  // Si el peso del enésimo artículo es // mayor que la capacidad de la mochila W, // entonces este artículo no puede // incluirse en la solución óptima si (wt[n - 1]> W) return knapSack(W, wt, val , norte - 1);  // Devuelve el máximo de dos casos: // (1) enésimo elemento incluido // (2) no incluido else return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), mochila(W, wt, val, n - 1));    // Código del controlador public static void Main() { int[] beneficio = new int[] { 60, 100, 120 };  int[] peso = nuevo int[] { 10, 20, 30 };  int W = 50;  int n = beneficio.Longitud;  Console.WriteLine(knapSack(W, peso, beneficio, n));  } } // Este código es aportado por Sam007>

 /* A Naive recursive implementation of  0-1 Knapsack problem */    // A utility function that returns  // maximum of two integers  function max(a, b)  {  return (a>b) ? a: b;  } // Devuelve el valor máximo que // se puede poner en una mochila de capacidad W function knapSack(W, wt, val, n) // Caso base if (n == 0 let beneficio = [ 60, 100, 120 ] ; sea peso = [ 10, 20, 30 ]; sea W = 50; sea n = beneficio.longitud; log(knapSack(W, peso, beneficio, n));PHP220>

Complejidad del tiempo: o(2^norte)
Espacio Auxiliar: O(N), espacio de pila necesario para la recursividad

Enfoque de programación dinámica para el problema de mochila 0/1

Enfoque de memorización para el problema de mochila 0/1:

Nota: Cabe señalar que la función anterior que utiliza recursividad calcula los mismos subproblemas una y otra vez. Consulte el siguiente árbol de recursividad, K(1, 1) se evalúa dos veces.

En el siguiente árbol de recursividad, k() se refiere a mochila(). Los dos parámetros indicados en el siguiente árbol de recursividad son n y W.
El árbol de recursividad sirve para las siguientes entradas de muestra.
peso[] = {1, 1, 1}, W = 2, beneficio[] = {10, 20, 30}

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)

Árbol de recursividad para Mochila con capacidad de 2 unidades y 3 artículos de 1 unidad de peso.

Como hay repeticiones del mismo subproblema una y otra vez podemos implementar la siguiente idea para resolver el problema.

Si tenemos un subproblema la primera vez, podemos resolverlo creando una matriz 2D que pueda almacenar un estado particular (n, w). Ahora, si volvemos a encontrar el mismo estado (n, w) en lugar de calcularlo en complejidad exponencial, podemos devolver directamente su resultado almacenado en la tabla en tiempo constante.

descargar turbo c++

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

// Here is the top-down approach of // dynamic programming #include  using namespace std; // Returns the value of maximum profit int knapSackRec(int W, int wt[], int val[], int index, int** dp) {  // base condition  if (index < 0)  return 0;  if (dp[index][W] != -1)  return dp[index][W];  if (wt[index]>W) { // Almacena el valor de la llamada a la función // apila en la tabla antes de regresar dp[index][W] = knapSackRec(W, wt, val, index - 1, dp);  devolver dp[índice][W];  } else { // Almacena el valor en una tabla antes de devolver dp[index][W] = max(val[index] + knapSackRec(W - wt[index], wt, val, index - 1, dp), knapSackRec(W , peso, valor, índice - 1, dp));  // Valor de retorno de la tabla después de almacenar return dp[index][W];  } } int knapSack(int W, int wt[], int val[], int n) { // doble puntero para declarar la // tabla dinámicamente int** dp;  dp = nuevo int*[n];  // bucle para crear la tabla dinámicamente for (int i = 0; i< n; i++)  dp[i] = new int[W + 1];  // loop to initially filled the  // table with -1  for (int i = 0; i < n; i++)  for (int j = 0; j < W + 1; j++)  dp[i][j] = -1;  return knapSackRec(W, wt, val, n - 1, dp); } // Driver Code int main() {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  cout << knapSack(W, weight, profit, n);  return 0; }>

// Here is the top-down approach of // dynamic programming import java.io.*; class GFG {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>b) ? a: b; } // Devuelve el valor de beneficio máximo static int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) W == 0) return 0;  si (dp[n][W]!= -1) devuelve dp[n][W];  if (wt[n - 1]> W) // Almacena el valor de la llamada a la función // apila en la tabla antes de regresar return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);  else // Valor de retorno de la tabla después de almacenar return dp[n][W] = max((val[n - 1] + knapSackRec(W - wt[n - 1], wt, val, n - 1, dp)) , knapSackRec(W, peso, valor, n - 1, dp));    static int knapSack(int W, int wt[], int val[], int N) { // Declara la tabla dinámicamente int dp[][] = new int[N + 1][W + 1];  // Bucle para llenar inicialmente la // tabla con -1 for (int i = 0; i< N + 1; i++)  for (int j = 0; j < W + 1; j++)  dp[i][j] = -1;  return knapSackRec(W, wt, val, N, dp);  }  // Driver Code  public static void main(String[] args)  {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int N = profit.length;  System.out.println(knapSack(W, weight, profit, N));  } } // This Code is contributed By FARAZ AHMAD>

# This is the memoization approach of # 0 / 1 Knapsack in Python in simple # we can say recursion + memoization = DP def knapsack(wt, val, W, n): # base conditions if n == 0 or W == 0: return 0 if t[n][W] != -1: return t[n][W] # choice diagram code if wt[n-1] <= W: t[n][W] = max( val[n-1] + knapsack( wt, val, W-wt[n-1], n-1), knapsack(wt, val, W, n-1)) return t[n][W] elif wt[n-1]>W: t[n][W] = mochila(wt, val, W, n-1) return t[n][W] # Código de conductor if __name__ == '__main__': beneficio = [60, 100, 120] peso = [10, 20, 30] W = 50 n = len(beneficio) # Inicializamos la matriz con -1 al principio. t = [[-1 para i en el rango (W + 1)] para j en el rango (n + 1)] print(mochila(peso, beneficio, W, n)) # Este código es una contribución de Prosun Kumar Sarkar>'>C# 
// A utility function that returns // maximum of two integers  function max(a, b)  {   return (a>b) ? a: b;  } // Devuelve el valor de beneficio máximo function knapSackRec(W, wt, val, n,dp) // Condición base if (n == 0 function knapSack( W, wt,val,N) { // Declara la tabla dp dinámicamente // Inicializando tablas dp (fila y columnas) con -1 debajo var dp = new Array(N+1).fill(-1).map(el => new Array(W+1).fill(-1) ); ; console.log(knapSack(W, peso, beneficio, N)); // Este código es aportado por akshitsaxenaa09.  
  Producción  
220>
  
    Complejidad del tiempo:    O (norte * oeste). Ya que se evitan cálculos redundantes de estados.  
    Espacio Auxiliar:    O(norte * W) + O(norte). El uso de una estructura de datos de matriz 2D para almacenar estados intermedios y el espacio de pila auxiliar (ASS) O(N) se ha utilizado para la pila de recursividad.
 
    Enfoque ascendente para el problema de mochila 0/1:    
Para resolver el problema siga la siguiente idea:
  
Dado que los subproblemas se evalúan nuevamente, este problema tiene la propiedad de subproblemas superpuestos. Entonces el problema de la mochila 0/1 tiene ambas propiedades (ver este y este ) de un problema de programación dinámica. Como otros típicos Problemas de programación dinámica (DP) , se puede evitar volver a calcular los mismos subproblemas construyendo una matriz temporal K[][] de manera ascendente.
 
    Ilustración:    
 
A continuación se muestra la ilustración del enfoque anterior:
cadena de java
  
Dejar,    peso[] = {1, 2, 3}, beneficio[] = {10, 15, 40}, Capacidad = 6    
 
Si no se completa ningún elemento, entonces el posible beneficio es 0.
weight⇢  
item⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
 
 
 
 
 
 
 
2
 
 
 
 
 
 
 
3
 
 
 
 
 
 
 
    Para llenar el primer artículo de la bolsa:    Si seguimos el procedimiento mencionado anteriormente, la tabla quedará como la siguiente.
weight⇢  
item⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
0
10
10
10
10
10
10
2
 
 
 
 
 
 
 
3
 
 
 
 
 
 
 
    Para llenar el segundo ítem:       
Cuando jthWeight = 2, entonces el beneficio máximo posible es max (10, DP[1][2-2] + 15) = max(10, 15) = 15.  
Cuando jthWeight = 3, entonces el beneficio máximo posible es max(2 no puesto, 2 se pone en la bolsa) = max(DP[1][3], 15+DP[1][3-2]) = max(10, 25) = 25.
weight⇢  
item⇣/
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
 
 
 
 
 
 
 
    Para completar el tercer ítem:     
Cuando jthWeight = 3, el beneficio máximo posible es max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.  
Cuando jthWeight = 4, el beneficio máximo posible es max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.  
Cuando jthWeight = 5, el beneficio máximo posible es max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.  
Cuando jthWeight = 6, el beneficio máximo posible es max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
weight⇢  
item⇣/
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
A continuación se muestra la implementación del enfoque anterior:
C++ 
// A dynamic programming based // solution for 0-1 Knapsack problem #include  using namespace std; // A utility function that returns // maximum of two integers int max(int a, int b) { return (a>b) ? a: b; } // Devuelve el valor máximo que // se puede poner en una mochila de capacidad W int knapSack(int W, int wt[], int val[], int n) { int i, w;  vector> K(n + 1, vector (W + 1));  // Construye la tabla K[][] de abajo hacia arriba para (i = 0; i<= n; i++) {  for (w = 0; w <= W; w++)   if (i == 0   }  return K[n][W]; } // Driver Code int main() {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  cout << knapSack(W, weight, profit, n);  return 0; } // This code is contributed by Debojyoti Mandal>
 C 
// A Dynamic Programming based // solution for 0-1 Knapsack problem #include  // A utility function that returns // maximum of two integers int max(int a, int b) { return (a>b) ? a: b; } // Devuelve el valor máximo que // se puede poner en una mochila de capacidad W int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[n + 1][W + 1];  // Construye la tabla K[][] de abajo hacia arriba para (i = 0; i<= n; i++) {  for (w = 0; w <= W; w++)   if (i == 0   }  return K[n][W]; } // Driver Code int main() {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  printf('%d', knapSack(W, weight, profit, n));  return 0; }>
 Java 
// A Dynamic Programming based solution // for 0-1 Knapsack problem import java.io.*; class Knapsack {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>b) ? a: b; } // Devuelve el valor máximo que // se puede poner en una mochila de capacidad W static int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[][] = nuevo int[n + 1][W + 1];  // Construye la tabla K[][] de abajo hacia arriba para (i = 0; i<= n; i++) {  for (w = 0; w <= W; w++)   if (i == 0   }  return K[n][W];  }  // Driver code  public static void main(String args[])  {  int profit[] = new int[] { 60, 100, 120 };  int weight[] = new int[] { 10, 20, 30 };  int W = 50;  int n = profit.length;  System.out.println(knapSack(W, weight, profit, n));  } } /*This code is contributed by Rajat Mishra */>
 Pitón 
# A Dynamic Programming based Python # Program for 0-1 Knapsack problem # Returns the maximum value that can # be put in a knapsack of capacity W def knapSack(W, wt, val, n): K = [[0 for x in range(W + 1)] for x in range(n + 1)] # Build table K[][] in bottom up manner for i in range(n + 1): for w in range(W + 1): if i == 0 or w == 0: K[i][w] = 0 elif wt[i-1] <= w: K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) else: K[i][w] = K[i-1][w] return K[n][W] # Driver code if __name__ == '__main__': profit = [60, 100, 120] weight = [10, 20, 30] W = 50 n = len(profit) print(knapSack(W, weight, profit, n)) # This code is contributed by Bhavya Jain>
 C# 
// A Dynamic Programming based solution for // 0-1 Knapsack problem using System; class GFG {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>b) ? a: b; } // Devuelve el valor máximo que // se puede poner en una mochila de // capacidad W static int knapSack(int W, int[] wt, int[] val, int n) { int i, w;  int[, ] K = nuevo int[n + 1, W + 1];  // Construye la tabla K[][] de abajo // hacia arriba para (i = 0; i<= n; i++) {  for (w = 0; w <= W; w++)   }  return K[n, W];  }  // Driver code  static void Main()  {  int[] profit = new int[] { 60, 100, 120 };  int[] weight = new int[] { 10, 20, 30 };  int W = 50;  int n = profit.Length;  Console.WriteLine(knapSack(W, weight, profit, n));  } } // This code is contributed by Sam007>
 JavaScript 
 // A Dynamic Programming based solution  // for 0-1 Knapsack problem    // A utility function that returns  // maximum of two integers  function max(a, b)  {  return (a>b) ? a: b;  } // Devuelve el valor máximo que // se puede poner en una mochila de capacidad W function knapSack(W, wt, val, n) { let i, w;  sea ​​K = nueva matriz (n + 1);    // Construye la tabla K[][] de abajo hacia arriba para (i = 0; i<= n; i++)  {  K[i] = new Array(W + 1);  for (w = 0; w <= W; w++)   w == 0)  K[i][w] = 0;  else if (wt[i - 1] <= w)  K[i][w]  = max(val[i - 1]  + K[i - 1][w - wt[i - 1]],  K[i - 1][w]);  else  K[i][w] = K[i - 1][w];    }    return K[n][W];  }    let profit = [ 60, 100, 120 ];  let weight = [ 10, 20, 30 ];  let W = 50;  let n = profit.length;  console.log(knapSack(W, weight, profit, n));>
 PHP 
 // A Dynamic Programming based solution // for 0-1 Knapsack problem // Returns the maximum value that // can be put in a knapsack of  // capacity W function knapSack($W, $wt, $val, $n) { $K = array(array()); // Build table K[][] in // bottom up manner for ($i = 0; $i <= $n; $i++) { for ($w = 0; $w <= $W; $w++)  } return $K[$n][$W]; } // Driver Code $profit = array(60, 100, 120); $weight = array(10, 20, 30); $W = 50; $n = count($profit); echo knapSack($W, $weight, $profit, $n); // This code is contributed by Sam007. ?>>
   
  Producción      Complejidad del tiempo:    O (norte * oeste). donde 'N' es el número de elementos y 'W' es la capacidad.  
    Espacio Auxiliar:    O (norte * oeste). El uso de una matriz 2-D de tamaño 'N*W'.
 
    Enfoque optimizado en espacio para el problema de mochila 0/1 mediante programación dinámica:    
Para resolver el problema siga la siguiente idea:
  
Para calcular la fila actual de la matriz dp[] solo necesitamos la fila anterior, pero si comenzamos a recorrer las filas de derecha a izquierda, entonces se puede hacer con una sola fila.
 
A continuación se muestra la implementación del enfoque anterior:
C++ 
// C++ program for the above approach #include  using namespace std; // Function to find the maximum profit int knapSack(int W, int wt[], int val[], int n) {  // Making and initializing dp array  int dp[W + 1];  memset(dp, 0, sizeof(dp));  for (int i = 1; i < n + 1; i++) {  for (int w = W; w>= 0; w--) { si (peso[i - 1]<= w)    // Finding the maximum value  dp[w] = max(dp[w],  dp[w - wt[i - 1]] + val[i - 1]);  }  }  // Returning the maximum value of knapsack  return dp[W]; } // Driver code int main() {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  cout << knapSack(W, weight, profit, n);  return 0; }>
 Java 
// Java program for the above approach import java.util.*; class GFG {  static int knapSack(int W, int wt[], int val[], int n)  {  // Making and initializing dp array  int[] dp = new int[W + 1];  for (int i = 1; i < n + 1; i++) {  for (int w = W; w>= 0; w--) { si (peso[i - 1]<= w)  // Finding the maximum value  dp[w]  = Math.max(dp[w], dp[w - wt[i - 1]]  + val[i - 1]);  }  }  // Returning the maximum value of knapsack  return dp[W];  }  // Driver code  public static void main(String[] args)  {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = profit.length;  System.out.print(knapSack(W, weight, profit, n));  } } // This code is contributed by gauravrajput1>
 Pitón 
# Python code to implement the above approach def knapSack(W, wt, val, n): # Making the dp array dp = [0 for i in range(W+1)] # Taking first i elements for i in range(1, n+1): # Starting from back, # so that we also have data of # previous computation when taking i-1 items for w in range(W, 0, -1): if wt[i-1] <= w: # Finding the maximum value dp[w] = max(dp[w], dp[w-wt[i-1]]+val[i-1]) # Returning the maximum value of knapsack return dp[W] # Driver code if __name__ == '__main__': profit = [60, 100, 120] weight = [10, 20, 30] W = 50 n = len(profit) print(knapSack(W, weight, profit, n)) # This code is contributed by Suyash Saxena>
 C# 
// Java program for the above approach using System; public class GFG {  static int knapSack(int W, int[] wt, int[] val, int n)  {  // Making and initializing dp array  int[] dp = new int[W + 1];  for (int i = 1; i < n + 1; i++) {  for (int w = W; w>= 0; w--) { si (peso[i - 1]<= w)  // Finding the maximum value  dp[w]  = Math.Max(dp[w], dp[w - wt[i - 1]]  + val[i - 1]);  }  }  // Returning the maximum value of knapsack  return dp[W];  }  // Driver code  public static void Main(String[] args)  {  int[] profit = { 60, 100, 120 };  int[] weight = { 10, 20, 30 };  int W = 50;  int n = profit.Length;  Console.Write(knapSack(W, weight, profit, n));  } } // This code is contributed by gauravrajput1>
 JavaScript 
 function knapSack(W , wt , val , n)  {  // Making and initializing dp array  var dp = Array(W + 1).fill(0);  for (i = 1; i < n + 1; i++) {  for (w = W; w>= 0; w--) { si (peso[i - 1]<= w)  // Finding the maximum value  dp[w] = Math.max(dp[w], dp[w - wt[i - 1]] + val[i - 1]);  }  }    // Returning the maximum value of knapsack  return dp[W];  }  // Driver code  var profit = [ 60, 100, 120 ];  var weight = [ 10, 20, 30 ];  var W = 50;  var n = profit.length;  console.log(knapSack(W, weight, profit, n)); // This code is contributed by Rajput-Ji>
   
  Producción  
220>
 
    Complejidad del tiempo    : O(NORTE * O). Como se evitan cálculos redundantes de estados  
    Espacio Auxiliar    : O(W) Como estamos usando una matriz 1-D en lugar de una matriz 2-D