Te doy la bienvenida a nuestra página web, en este sitio hallarás la respuesta de lo que buscabas.
Solución:
¿Qué intentaste?
La idea, dado el problema que planteó (que especifica que debemos usar la recursividad) es simple: para cada elemento que pueda tomar, vea si es mejor tomarlo o no. Entonces solo hay dos caminos posibles:
- tu tomas el articulo
- no lo tomas
Cuando toma el artículo, lo elimina de su lista y disminuye la capacidad por el peso del artículo.
Cuando no toma el artículo, lo elimina de su lista pero no disminuye la capacidad.
A veces es útil imprimir el aspecto que pueden tener las llamadas recursivas. En este caso, podría verse así:
Calling 11 8 7 6 5 with cap: 20
+Calling 8 7 6 5 with cap: 20
| Calling 7 6 5 with cap: 20
| Calling 6 5 with cap: 20
| Calling 5 with cap: 20
| Result: 5
| Calling 5 with cap: 14
| Result: 5
| Result: 11
| Calling 6 5 with cap: 13
| Calling 5 with cap: 13
| Result: 5
| Calling 5 with cap: 7
| Result: 5
| Result: 11
| Result: 18
| Calling 7 6 5 with cap: 12
| Calling 6 5 with cap: 12
| Calling 5 with cap: 12
| Result: 5
| Calling 5 with cap: 6
| Result: 5
| Result: 11
| Calling 6 5 with cap: 5
| Calling 5 with cap: 5
| Result: 5
| Result: 5
| Result: 12
+Result: 20
Calling 8 7 6 5 with cap: 9
Calling 7 6 5 with cap: 9
Calling 6 5 with cap: 9
Calling 5 with cap: 9
Result: 5
Calling 5 with cap: 3
Result: 0
Result: 6
Calling 6 5 with cap: 2
Calling 5 with cap: 2
Result: 0
Result: 0
Result: 7
Calling 7 6 5 with cap: 1
Calling 6 5 with cap: 1
Calling 5 with cap: 1
Result: 0
Result: 0
Result: 0
Result: 8
Result: 20
Lo hice a propósito mostrar la llamada a [8 7 6 5] con una capacidad de 20, lo que da un resultado de 20 (8 + 7 + 5).
Tenga en cuenta que [8 7 6 5] se llama dos veces: una con capacidad para 20 (porque no tomamos 11) y una vez con capacidad para 9 (porque sí tomó 11).
Entonces, el camino hacia la solución:
11 no tomado, llamando [8 7 6 5] con capacidad para 20
8 tomado, llamando [7 6 5] con capacidad para 12 (20 – 8)
7 tomado, llamando [6 5] con capacidad para 5 (12 – 7)
6 no tomado, llamando [5] con capacidad para 5
5 tomados, estamos en cero.
El método real en Java puede caber en muy pocas líneas de código.
Como obviamente esto es tarea, solo te ayudaré con un esqueleto:
private int ukp( final int[] ar, final int cap )
if ( ar.length == 1 )
return ar[0] <= cap ? ar[0] : 0;
else
final int[] nar = new int[ar.length-1];
System.arraycopy(ar, 1, nar, 0, nar.length);
fint int item = ar[0];
if ( item < cap )
final int left = ... // fill me: we're not taking the item
final int took = ... // fill me: we're taking the item
return Math.max(took,left);
else
return ... // fill me: we're not taking the item
Copié la matriz a una nueva matriz, que es menos eficiente (pero de todos modos la recursividad no es el camino a seguir aquí si busca rendimiento), pero más "funcional".
Tuve que hacer esto para mi tarea, así que probé todos los códigos anteriores (excepto el de Python), pero ninguno de ellos funciona para todos los casos de esquina.
Este es mi código, funciona para todos los casos de esquina.
static int[] values = new int[] 894, 260, 392, 281, 27;
static int[] weights = new int[] 8, 6, 4, 0, 21;
static int W = 30;
private static int knapsack(int i, int W)
if (i < 0)
return 0;
if (weights[i] > W)
return knapsack(i-1, W);
else
return Math.max(knapsack(i-1, W), knapsack(i-1, W - weights[i]) + values[i]);
public static void main(String[] args)
System.out.println(knapsack(values.length - 1, W));
No está optimizado, la recursividad lo matará, pero puede usar una simple memorización para solucionarlo. ¿Por qué mi código es corto, correcto y fácil de entender? Acabo de ver la definición matemática del problema de la mochila 0-1 http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming
El problema es básicamente una versión modificada del problema clásico de la mochila por simplicidad (hay no hay valores / beneficios correspondiente a los pesos) (para real: http://en.wikipedia.org/wiki/Knapsack_problem, 0/1 Mochila - Algunas aclaraciones sobre el pseudocódigo de Wiki, ¿Cómo entender que el problema de la mochila es NP-completo? problema pseudopolinomio ?, http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/).
Aquí hay cinco versiones para resolver esto en c #:
versión 1: Uso de programación dinámica (tabulado - buscando ansiosamente soluciones para todos los problemas de suma para llegar al final) - O (n * W)
versión 2: Uso de DP pero versión de memorización (perezoso, solo para encontrar soluciones para lo que sea necesario)
versión 3 Uso de la recursividad para demostrar subproblemas superpuestos y subestructura óptima
versión 4 Recursivo (fuerza bruta): respuesta básicamente aceptada
versión 5 Usando la pila de # 4 (demostrando la eliminación de la recursividad de la cola)
versión 1: Uso de programación dinámica (tabulado - buscando ansiosamente soluciones para todos los problemas de suma para llegar al final) - O (n * W)
public bool KnapsackSimplified_DP_Tabulated_Eager(int[] weights, int W)
this.Validate(weights, W);
bool[][] DP_Memoization_Cache = new bool[weights.Length + 1][];
for (int i = 0; i <= weights.Length; i++)
DP_Memoization_Cache[i] = new bool[W + 1];
for (int i = 1; i <= weights.Length; i++)
for (int w = 0; w <= W; w++)
f(i-1, w-weights[i-1])
if(weights[i-1] == w)
DP_Memoization_Cache[i][w] = true;
else
DP_Memoization_Cache[i][w] = DP_Memoization_Cache[i - 1][w];
if(!DP_Memoization_Cache[i][w])
if (w > weights[i - 1])
DP_Memoization_Cache[i][w] = DP_Memoization_Cache[i - 1][w - weights[i - 1]];
return DP_Memoization_Cache[weights.Length][W];
versión 2: Uso de DP pero versión de memorización (perezoso, solo para encontrar soluciones para lo que sea necesario)
///
/// f(i, w) determines if weight 'w' can be accumulated using given 'i' number of weights
/// f(i, w) = False if i < 0
/// OR True if weights[i] == w
/// OR f(i-1, w) if weights[i] > w
/// OR f(i-1, w) || f(i-1, w-weights[i])
///
///
/// Note, its index of row in the cache
/// index of given weifhts is indexOfCahce -1 (as it starts from 0)
///
bool KnapsackSimplified_DP_Memoization_Lazy(int[] weights, int w, int i_rowIndexOfCache, bool?[][] DP_Memoization_Cache)
if(i_rowIndexOfCache < 0)
return false;
if(DP_Memoization_Cache[i_rowIndexOfCache][w].HasValue)
return DP_Memoization_Cache[i_rowIndexOfCache][w].Value;
int i_weights_index = i_rowIndexOfCache - 1;
if (weights[i_weights_index] == w)
//we can just use current weight, so no need to call other recursive methods
//just return true
DP_Memoization_Cache[i_rowIndexOfCache][w] = true;
return true;
//see if W, can be achieved without using weights[i]
bool flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights,
w, i_rowIndexOfCache - 1);
DP_Memoization_Cache[i_rowIndexOfCache][w] = flag;
if (flag)
return true;
if (w > weights[i_weights_index])
//see if W-weight[i] can be achieved with rest of the weights
flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights,
w - weights[i_weights_index], i_rowIndexOfCache - 1);
DP_Memoization_Cache[i_rowIndexOfCache][w] = flag;
return flag;
dónde
public bool KnapsackSimplified_DP_Memoization_Lazy(int[] weights, int W)
this.Validate(weights, W);
//note 'row' index represents the number of weights been used
//note 'colum' index represents the weight that can be achived using given
//number of weights 'row'
bool?[][] DP_Memoization_Cache = new bool?[weights.Length+1][];
for(int i = 0; i<=weights.Length; i++)
DP_Memoization_Cache[i] = new bool?[W + 1];
for(int w=0; w<=W; w++)
if(i != 0)
DP_Memoization_Cache[i][w] = null;
else
//can't get to weight 'w' using none of the given weights
DP_Memoization_Cache[0][w] = false;
DP_Memoization_Cache[i][0] = false;
bool f = this.KnapsackSimplified_DP_Memoization_Lazy(
weights, w: W, i_rowIndexOfCache: weights.Length, DP_Memoization_Cache: DP_Memoization_Cache);
Assert.IsTrue(f == DP_Memoization_Cache[weights.Length][W]);
return f;
versión 3 Identificación de subproblemas superpuestos y subestructura óptima
///
/// f(i, w) = False if i < 0
/// OR True if weights[i] == w
/// OR f(i-1, w) if weights[i] > w
/// OR f(i-1, w) || f(i-1, w-weights[i])
///
public bool KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(int[] weights, int W, int i)
if(i<0)
//no more weights to traverse
return false;
if(weights[i] == W)
//we can just use current weight, so no need to call other recursive methods
//just return true
return true;
//see if W, can be achieved without using weights[i]
bool flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights,
W, i - 1);
if(flag)
return true;
if(W > weights[i])
//see if W-weight[i] can be achieved with rest of the weights
return this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, W - weights[i], i - 1);
return false;
dónde
public bool KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(int[] weights, int W)
this.Validate(weights, W);
bool f = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, W,
i: weights.Length - 1);
return f;
versión 4 Fuerza bruta
private bool KnapsackSimplifiedProblemRecursive(int[] weights, int sum, int currentSum, int index, List itemsInTheKnapsack)
if (currentSum == sum)
return true;
if (currentSum > sum)
return false;
if (index >= weights.Length)
return false;
itemsInTheKnapsack.Add(weights[index]);
bool flag = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum: currentSum + weights[index],
index: index + 1, itemsInTheKnapsack: itemsInTheKnapsack);
if (!flag)
itemsInTheKnapsack.Remove(weights[index]);
flag = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum, index + 1, itemsInTheKnapsack);
return flag;
public bool KnapsackRecursive(int[] weights, int sum, out List knapsack)
if(sum <= 0)
throw new ArgumentException("sum should be +ve non zero integer");
knapsack = new List();
bool fits = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum: 0, index: 0,
itemsInTheKnapsack: knapsack);
return fits;
versión 5: versión iterativa usando pila (nota - misma complejidad - usando pila - eliminando la recursividad de cola)
public bool KnapsackIterativeUsingStack(int[] weights, int sum, out List knapsack)
dónde
class KnapsackStackNode
public int sumOfWeightsInTheKnapsack;
public int nextItemIndex;
public bool alreadyExploredAdjuscentItems;
public bool includesItemAtCurrentIndex;
Y pruebas unitarias
[TestMethod]
public void KnapsackSimpliedProblemTests()
int[] weights = new int[] 7, 5, 4, 4, 1 ;
List bag = null;
bool flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 10, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(5));
Assert.IsTrue(bag.Contains(4));
Assert.IsTrue(bag.Contains(1));
Assert.IsTrue(bag.Count == 3);
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 3, knapsack: out bag);
Assert.IsFalse(flag);
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 7, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(7));
Assert.IsTrue(bag.Count == 1);
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 1, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(1));
Assert.IsTrue(bag.Count == 1);
flag = this.KnapsackSimplified_DP_Tabulated_Eager(weights, 10);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_DP_Tabulated_Eager(weights, 3);
Assert.IsFalse(flag);
flag = this.KnapsackSimplified_DP_Tabulated_Eager(weights, 7);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_DP_Tabulated_Eager(weights, 1);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_DP_Memoization_Lazy(weights, 10);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_DP_Memoization_Lazy(weights, 3);
Assert.IsFalse(flag);
flag = this.KnapsackSimplified_DP_Memoization_Lazy(weights, 7);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_DP_Memoization_Lazy(weights, 1);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 10);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 3);
Assert.IsFalse(flag);
flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 7);
Assert.IsTrue(flag);
flag = this.KnapsackSimplified_OverlappedSubPromblems_OptimalSubstructure(weights, 1);
Assert.IsTrue(flag);
flag = this.KnapsackRecursive(weights, 10, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(5));
Assert.IsTrue(bag.Contains(4));
Assert.IsTrue(bag.Contains(1));
Assert.IsTrue(bag.Count == 3);
flag = this.KnapsackRecursive(weights, 3, knapsack: out bag);
Assert.IsFalse(flag);
flag = this.KnapsackRecursive(weights, 7, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(7));
Assert.IsTrue(bag.Count == 1);
flag = this.KnapsackRecursive(weights, 1, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(1));
Assert.IsTrue(bag.Count == 1);
weights = new int[] 11, 8, 7, 6, 5 ;
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 20, knapsack: out bag);
Assert.IsTrue(bag.Contains(8));
Assert.IsTrue(bag.Contains(7));
Assert.IsTrue(bag.Contains(5));
Assert.IsTrue(bag.Count == 3);
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 27, knapsack: out bag);
Assert.IsFalse(flag);
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 11, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(11));
Assert.IsTrue(bag.Count == 1);
flag = this.KnapsackSimplifiedProblemIterativeUsingStack(weights, 5, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(5));
Assert.IsTrue(bag.Count == 1);
flag = this.KnapsackRecursive(weights, 20, knapsack: out bag);
Assert.IsTrue(bag.Contains(8));
Assert.IsTrue(bag.Contains(7));
Assert.IsTrue(bag.Contains(5));
Assert.IsTrue(bag.Count == 3);
flag = this.KnapsackRecursive(weights, 27, knapsack: out bag);
Assert.IsFalse(flag);
flag = this.KnapsackRecursive(weights, 11, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(11));
Assert.IsTrue(bag.Count == 1);
flag = this.KnapsackRecursive(weights, 5, knapsack: out bag);
Assert.IsTrue(flag);
Assert.IsTrue(bag.Contains(5));
Assert.IsTrue(bag.Count == 1);