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>
Producción
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>
Producción
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