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 arrays de enteros val[0..n-1] y wt[0..n-1] que representan valores y pesos asociados con n elementos respectivamente. También dado un número entero W que representa la capacidad de la mochila, encuentre el subconjunto de valor máximo de val[] tal que la suma de los pesos de este subconjunto sea menor o igual a W. No podemos romper un artículo, elegir el artículo completo o no no elegirlo (propiedad 0-1).
Aquí W <= 2000000 y n <= 500
Ejemplos:
Entrada: W = 10, n = 3
val[] = {7, 8, 4}
wt[] = {3, 8, 6}
Salida: 11
Explicación: Obtenemos el valor máximo seleccionando artículos de 3 KG y 6 KG.
Hemos discutido una solución basada en Programación Dinámica aquí . En la solución anterior, usamos una array * W. Podemos reducir el espacio extra utilizado. La idea detrás de la optimización es que, para calcular mat[i][j], solo necesitamos la solución de la fila anterior. En el problema de la mochila 0-1, si actualmente estamos en mat[i][j] e incluimos el i-ésimo elemento, entonces movemos j-wt[i] pasos hacia atrás en la fila anterior y si excluimos el elemento actual, nos movemos en la j-ésima columna en la fila anterior. Entonces aquí podemos observar que a la vez estamos trabajando solo con 2 filas consecutivas.
En la siguiente solución, creamos una array de tamaño 2*W. Si n es impar, la respuesta final será mat[0][W] y si n es par, la respuesta final será mat[1][W] porque el índice comienza en 0.
C++
// C++ program of a space optimized DP solution for // 0-1 knapsack problem. #include<bits/stdc++.h> using namespace std; // val[] is for storing maximum profit for each weight // wt[] is for storing weights // n number of item // W maximum capacity of bag // mat[2][W+1] to store final result int KnapSack(int val[], int wt[], int n, int W) { // matrix to store final result int mat[2][W+1]; memset(mat, 0, sizeof(mat)); // iterate through all items int i = 0; while (i < n) // one by one traverse each element { int j = 0; // traverse all weights j <= W // if i is odd that mean till now we have odd // number of elements so we store result in 1th // indexed row if (i%2!=0) { while (++j <= W) // check for each value { if (wt[i] <= j) // include element mat[1][j] = max(val[i] + mat[0][j-wt[i]], mat[0][j] ); else // exclude element mat[1][j] = mat[0][j]; } } // if i is even that mean till now we have even number // of elements so we store result in 0th indexed row else { while(++j <= W) { if (wt[i] <= j) mat[0][j] = max(val[i] + mat[1][j-wt[i]], mat[1][j]); else mat[0][j] = mat[1][j]; } } i++; } // Return mat[0][W] if n is odd, else mat[1][W] return (n%2 != 0)? mat[0][W] : mat[1][W]; } // Driver program to test the cases int main() { int val[] = {7, 8, 4}, wt[] = {3, 8, 6}, W = 10, n = 3; cout << KnapSack(val, wt, n, W) << endl; return 0; }
Java
// Java program of a space optimized DP solution for // 0-1 knapsack problem. class GFG { // val[] is for storing maximum // profit for each weight // wt[] is for storing weights // n number of item // W maximum capacity of bag // mat[2][W+1] to store final result static int KnapSack(int val[], int wt[], int n, int W) { // matrix to store final result int mat[][] = new int[2][W + 1]; // iterate through all items int i = 0; while (i < n) // one by one traverse each element { int j = 0; // traverse all weights j <= W // if i is odd that mean till now we have odd // number of elements so we store result in 1th // indexed row if (i % 2 != 0) { while (++j <= W) // check for each value { if (wt[i] <= j) // include element { mat[1][j] = Math.max(val[i] + mat[0][j - wt[i]], mat[0][j]); } else // exclude element { mat[1][j] = mat[0][j]; } } } // if i is even that means till now // we have even number of elements // so we store result in 0th indexed row else { while (++j <= W) { if (wt[i] <= j) { mat[0][j] = Math.max(val[i] + mat[1][j - wt[i]], mat[1][j]); } else { mat[0][j] = mat[1][j]; } } } i++; } // Return mat[0][W] if n is odd, else mat[1][W] return (n % 2 != 0) ? mat[0][W] : mat[1][W]; } // Driver Code public static void main(String[] args) { int val[] = {7, 8, 4}, wt[] = {3, 8, 6}, W = 10, n = 3; System.out.println(KnapSack(val, wt, n, W)); } } // This code is contributed by PrinciRaj1992
Python3
# Python program of a space # optimized DP solution for # 0-1 knapsack problem. # val[] is for storing maximum # profit for each weight # wt[] is for storing weights # n number of item # W maximum capacity of bag # mat[2][W+1] to store final result def KnapSack(val, wt, n, W): # matrix to store final result mat = [[0 for i in range(W + 1)] for i in range(2)] # iterate through all items i = 0 while i < n: # one by one traverse # each element j = 0 # traverse all weights j <= W # if i is odd that mean till # now we have odd number of # elements so we store result # in 1th indexed row if i % 2 == 0: while j < W: # check for each value j += 1 if wt[i] <= j: # include element mat[1][j] = max(val[i] + mat[0][j - wt[i]], mat[0][j]) else: # exclude element mat[1][j] = mat[0][j] # if i is even that mean till # now we have even number # of elements so we store # result in 0th indexed row else: while j < W: j += 1 if wt[i] <= j: mat[0][j] = max(val[i] + mat[1][j - wt[i]], mat[1][j]) else: mat[0][j] = mat[1][j] i += 1 # Return mat[0][W] if n is # odd, else mat[1][W] if n % 2 == 0: return mat[0][W] else: return mat[1][W] # Driver code val = [7, 8, 4] wt = [3, 8, 6] W = 10 n = 3 print(KnapSack(val, wt, n, W)) # This code is contributed # by sahilshelangia
C#
// C# program of a space optimized DP solution for // 0-1 knapsack problem. using System; class GFG { // val[] is for storing maximum // profit for each weight // wt[] is for storing weights // n number of item // W maximum capacity of bag // mat[2,W+1] to store final result static int KnapSack(int []val, int []wt, int n, int W) { // matrix to store final result int [,]mat = new int[2, W + 1]; // iterate through all items int i = 0; while (i < n) // one by one traverse each element { int j = 0; // traverse all weights j <= W // if i is odd that mean till now we have odd // number of elements so we store result in 1th // indexed row if (i % 2 != 0) { while (++j <= W) // check for each value { if (wt[i] <= j) // include element { mat[1, j] = Math.Max(val[i] + mat[0, j - wt[i]], mat[0, j]); } else // exclude element { mat[1,j] = mat[0,j]; } } } // if i is even that means till now // we have even number of elements // so we store result in 0th indexed row else { while (++j <= W) { if (wt[i] <= j) { mat[0, j] = Math.Max(val[i] + mat[1, j - wt[i]], mat[1, j]); } else { mat[0, j] = mat[1, j]; } } } i++; } // Return mat[0,W] if n is odd, else mat[1,W] return (n % 2 != 0) ? mat[0, W] : mat[1, W]; } // Driver Code public static void Main(String[] args) { int []val = {7, 8, 4}; int []wt = {3, 8, 6}; int W = 10, n = 3; Console.WriteLine(KnapSack(val, wt, n, W)); } } // This code is contributed by 29AjayKumar
PHP
<?php // PHP program of a space optimized DP // solution for 0-1 knapsack problem. // val[] is for storing maximum profit // for each weight wt[] is for storing // weights n number of item // W maximum capacity of bag // mat[2][W+1] to store final result function KnapSack(&$val, &$wt, $n, $W) { // matrix to store final result $mat = array_fill(0, 2, array_fill(0, $W + 1, NULL)); // iterate through all items $i = 0; while ($i < $n) // one by one traverse // each element { $j = 0; // traverse all weights j <= W // if i is odd that mean till now we // have odd number of elements so we // store result in 1th indexed row if ($i % 2 != 0) { while (++$j <= $W) // check for each value { if ($wt[$i] <= $j) // include element $mat[1][$j] = max($val[$i] + $mat[0][$j - $wt[$i]], $mat[0][$j]); else // exclude element $mat[1][$j] = $mat[0][$j]; } } // if i is even that mean till now we have // even number of elements so we store result // in 0th indexed row else { while(++$j <= $W) { if ($wt[$i] <= $j) $mat[0][$j] = max($val[$i] + $mat[1][$j - $wt[$i]], $mat[1][$j]); else $mat[0][$j] = $mat[1][$j]; } } $i++; } // Return mat[0][W] if n is odd, // else mat[1][W] if ($n % 2 != 0) return $mat[0][$W]; else return $mat[1][$W]; } // Driver Code $val = array(7, 8, 4); $wt = array(3, 8, 6); $W = 10; $n = 3; echo KnapSack($val, $wt, $n, $W) . "\n"; // This code is contributed // by Akanksha Rai ?>
Javascript
<script> // Javascript program of a space optimized DP solution for // 0-1 knapsack problem. // val[] is for storing maximum // profit for each weight // wt[] is for storing weights // n number of item // W maximum capacity of bag // mat[2][W+1] to store final result function KnapSack(val, wt, n, W) { // matrix to store final result let mat = new Array(2); for(let i = 0; i < 2; i++) { mat[i] = new Array(W + 1); } for(let i = 0; i < 2; i++) { for(let j = 0; j < W + 1; j++) { mat[i][j] = 0; } } // iterate through all items let i = 0; while (i < n) // one by one traverse each element { let j = 0; // traverse all weights j <= W // if i is odd that mean till now we have odd // number of elements so we store result in 1th // indexed row if (i % 2 != 0) { while (++j <= W) // check for each value { if (wt[i] <= j) // include element { mat[1][j] = Math.max(val[i] + mat[0][j - wt[i]], mat[0][j]); } else // exclude element { mat[1][j] = mat[0][j]; } } } // if i is even that means till now // we have even number of elements // so we store result in 0th indexed row else { while (++j <= W) { if (wt[i] <= j) { mat[0][j] = Math.max(val[i] + mat[1][j - wt[i]], mat[1][j]); } else { mat[0][j] = mat[1][j]; } } } i++; } // Return mat[0][W] if n is odd, else mat[1][W] return (n % 2 != 0) ? mat[0][W] : mat[1][W]; } let val=[7, 8, 4]; let wt=[3, 8, 6]; let W = 10, n = 3; document.write(KnapSack(val, wt, n, W)); // This code is contributed by rag2127 </script>
11
Complejidad temporal: O(n * W)
Espacio auxiliar: O(W)
Aquí hay un código optimizado aportado por Gaurav Mamgain
C++14
// C++ program of a space optimized DP solution for // 0-1 knapsack problem. #include<bits/stdc++.h> using namespace std; // val[] is for storing maximum profit for each weight // wt[] is for storing weights // n number of item // W maximum capacity of bag // dp[W+1] to store final result int KnapSack(int val[], int wt[], int n, int W) { // array to store final result //dp[i] stores the profit with KnapSack capacity "i" int dp[W+1]; //initially profit with 0 to W KnapSack capacity is 0 memset(dp, 0, sizeof(dp)); // iterate through all items for(int i=0; i < n; i++) //traverse dp array from right to left for(int j=W; j>=wt[i]; j--) dp[j] = max(dp[j] , val[i] + dp[j-wt[i]]); /*above line finds out maximum of dp[j](excluding ith element value) and val[i] + dp[j-wt[i]] (including ith element value and the profit with "KnapSack capacity - ith element weight") */ return dp[W]; } // Driver program to test the cases int main() { int val[] = {7, 8, 4}, wt[] = {3, 8, 6}, W = 10, n = 3; cout << KnapSack(val, wt, n, W) << endl; return 0; } // This code is contributed by Gaurav Mamgain
Java
// Java program of a space optimized DP solution for // 0-1 knapsack problem. import java.util.Arrays; class GFG { // val[] is for storing maximum profit for each weight // wt[] is for storing weights // n number of item // W maximum capacity of bag // dp[W+1] to store final result static int KnapSack(int val[], int wt[], int n, int W) { // array to store final result //dp[i] stores the profit with KnapSack capacity "i" int []dp = new int[W+1]; //initially profit with 0 to W KnapSack capacity is 0 Arrays.fill(dp, 0); // iterate through all items for(int i=0; i < n; i++) //traverse dp array from right to left for(int j = W; j >= wt[i]; j--) dp[j] = Math.max(dp[j] , val[i] + dp[j - wt[i]]); /*above line finds out maximum of dp[j](excluding ith element value) and val[i] + dp[j-wt[i]] (including ith element value and the profit with "KnapSack capacity - ith element weight") */ return dp[W]; } // Driver code public static void main(String[] args) { int val[] = {7, 8, 4}, wt[] = {3, 8, 6}, W = 10, n = 3; System.out.println(KnapSack(val, wt, n, W)); } } // This code is contributed by Princi Singh
Python3
# Python program of a space optimized DP solution for # 0-1 knapsack problem. # val[] is for storing maximum profit for each weight # wt[] is for storing weights # n number of item # W maximum capacity of bag # dp[W+1] to store final result def KnapSack(val, wt, n, W): # array to store final result # dp[i] stores the profit with KnapSack capacity "i" dp = [0]*(W+1); # iterate through all items for i in range(n): #traverse dp array from right to left for j in range(W,wt[i]-1,-1): dp[j] = max(dp[j] , val[i] + dp[j-wt[i]]); '''above line finds out maximum of dp[j](excluding ith element value) and val[i] + dp[j-wt[i]] (including ith element value and the profit with "KnapSack capacity - ith element weight") *''' return dp[W]; # Driver program to test the cases val = [7, 8, 4]; wt = [3, 8, 6]; W = 10; n = 3; print(KnapSack(val, wt, n, W)); # This code is contributed by Princi Singh
C#
// C# program of a space optimized DP solution for // 0-1 knapsack problem. using System; class GFG { // val[] is for storing maximum profit for each weight // wt[] is for storing weights // n number of item // W maximum capacity of bag // dp[W+1] to store final result static int KnapSack(int []val, int []wt, int n, int W) { // array to store final result //dp[i] stores the profit with KnapSack capacity "i" int []dp = new int[W + 1]; //initially profit with 0 to W KnapSack capacity is 0 for(int i = 0; i < W + 1; i++) dp[i] = 0; // iterate through all items for(int i = 0; i < n; i++) //traverse dp array from right to left for(int j = W; j >= wt[i]; j--) dp[j] = Math.Max(dp[j] , val[i] + dp[j - wt[i]]); /*above line finds out maximum of dp[j](excluding ith element value) and val[i] + dp[j-wt[i]] (including ith element value and the profit with "KnapSack capacity - ith element weight") */ return dp[W]; } // Driver code public static void Main(String[] args) { int []val = {7, 8, 4}; int []wt = {3, 8, 6}; int W = 10, n = 3; Console.WriteLine(KnapSack(val, wt, n, W)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript program of a space optimized DP solution for // 0-1 knapsack problem. // val[] is for storing maximum profit for each weight // wt[] is for storing weights // n number of item // W maximum capacity of bag // dp[W+1] to store final result function KnapSack(val,wt,n,W) { // array to store final result // dp[i] stores the profit with KnapSack capacity "i" let dp = new Array(W+1); // initially profit with 0 to W KnapSack capacity is 0 for(let i=0;i<W+1;i++) { dp[i]=0; } // iterate through all items for(let i=0; i < n; i++) // traverse dp array from right to left for(let j = W; j >= wt[i]; j--) dp[j] = Math.max(dp[j] , val[i] + dp[j - wt[i]]); /*above line finds out maximum of dp[j] (excluding ith element value)and val[i] + dp[j-wt[i]] (including ith element value and the profit with "KnapSack capacity - ith element weight") */ return dp[W]; } // Driver code let val=[7, 8, 4]; let wt=[3, 8, 6]; let W = 10, n = 3; document.write(KnapSack(val, wt, n, W)); // This code is contributed by avanitrachhadiya2155 </script>
11
Este artículo es una contribución de Shashank Mishra (Gullu) . Este artículo está revisado por el equipo geeksforgeeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA