algorithm
Problema de mochila
Buscar..
Observaciones
El problema de la mochila surge principalmente en los mecanismos de asignación de recursos. El nombre "Mochila" fue introducido por primera vez por Tobias Dantzig .
Espacio auxiliar: O(nw)
Complejidad del tiempo O(nw)
Fundamentos del problema de la mochila
El problema : dado un conjunto de elementos en los que cada elemento contiene un peso y un valor, determine el número de cada uno para incluir en una colección de modo que el peso total sea menor o igual a un límite dado y el valor total sea lo más grande posible .
Pseudo código para problema de mochila
Dado:
- Valores (array v)
- Pesos (matriz w)
- Número de elementos distintos (n)
- Capacidad (W)
for j from 0 to W do:
m[0, j] := 0
for i from 1 to n do:
for j from 0 to W do:
if w[i] > j then:
m[i, j] := m[i-1, j]
else:
m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
Una implementación simple del pseudo código anterior usando Python:
def knapSack(W, wt, val, n):
K = [[0 for x in range(W+1)] for x in range(n+1)]
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]
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))
Ejecutando el código: Guarde esto en un archivo llamado knapSack.py
$ python knapSack.py
220
Complejidad temporal del código anterior: O(nW)
donde n es el número de elementos y W es la capacidad de la mochila.
Solución implementada en C #
public class KnapsackProblem
{
private static int Knapsack(int w, int[] weight, int[] value, int n)
{
int i;
int[,] k = new int[n + 1, w + 1];
for (i = 0; i <= n; i++)
{
int b;
for (b = 0; b <= w; b++)
{
if (i==0 || b==0)
{
k[i, b] = 0;
}
else if (weight[i - 1] <= b)
{
k[i, b] = Math.Max(value[i - 1] + k[i - 1, b - weight[i - 1]], k[i - 1, b]);
}
else
{
k[i, b] = k[i - 1, b];
}
}
}
return k[n, w];
}
public static int Main(int nItems, int[] weights, int[] values)
{
int n = values.Length;
return Knapsack(nItems, weights, values, n);
}
}