¿Cómo resuelvo el algoritmo de mochila ‘clásico’ recursivamente?

Esta es mi tarea

The Knapsack Problem es un clásico de la informática. En su forma más simple, implica tratar de colocar artículos de diferentes pesos en una mochila para que la mochila termine con un peso total especificado. No necesita caber en todos los artículos. Por ejemplo, supongamos que quiere que su mochila pese exactamente 20 libras, y tiene cinco artículos, con pesos de 11, 8, 7, 6 y 5 libras. Para pequeñas cantidades de elementos, los humanos son bastante buenos para resolver este problema mediante inspección. Por lo tanto, probablemente pueda darse cuenta de que solo la combinación de 8, 7 y 5 elementos sum 20.

Realmente no sé por dónde empezar a escribir este algoritmo. Entiendo la recursión cuando se aplica a números de factoriales y triangularjs. Sin embargo, estoy perdido en este momento.

¿Qué intentaste?

La idea, dado el problema que usted indicó (que especifica que debemos usar recursividad) es simple: para cada artículo que puede tomar, vea si es mejor tomarlo o no. Entonces solo hay dos caminos posibles:

  1. tomas el objeto
  2. 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 retira de su lista, pero no disminuye la capacidad.

A veces ayuda imprimir lo que pueden parecer 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 

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 vez con una capacidad de 20 (porque no tomamos 11) y una vez con una capacidad de 9 (porque con tomó 11).

Entonces el camino a la solución:

11 no tomado, llamando [8 7 6 5] con una capacidad de 20

8 tomados, llamando [7 6 5] con una capacidad de 12 (20 – 8)

7 tomados, llamando a [6 5] con una capacidad de 5 (12 – 7)

6 no tomado, llamando a [5] con una capacidad de 5

5 tomado, estamos en cero.

El método real en Java puede caber en muy pocas líneas de código.

Dado que esto es obviamente una tarea, 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 si buscas rendimiento), pero es 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 en todos los rincones.

Este es mi código, funciona para cada caso 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 recursión te matará, pero puedes usar la memoria simple para arreglar eso. ¿Por qué mi código es corto, correcto y simple de entender? Acabo de ver la definición matemática del problema 0-1 Knapsack http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

El problema es básicamente la versión modificada del clásico problema de mochila para simplificar (no hay valores / beneficios correspondientes a los pesos) (para real: http://en.wikipedia.org/wiki/Knapsack_problem , 0/1 Knapsack – Algunas aclaraciones sobre El seudocódigo de Wiki , ¿Cómo entender el problema de la mochila es NP-completo?, ¿Por qué el problema de la mochila se llama pseudo-polinomio?, http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem / ).

Aquí hay cinco versiones de resolver esto en c #:

version1 : Uso de progtwigción dinámica (tabulada – buscando con entusiasmo soluciones para todos los problemas de sum para llegar a la final) – O (n * W)

versión 2 : Uso de la versión de DP pero de memoria (flojo, simplemente encontrando soluciones para lo que sea necesario)

versión 3 Uso de la recursión para demostrar los sub problemas superpuestos y la subestructura óptima

versión 4 Recursiva (fuerza bruta): respuesta básicamente aceptada

versión 5 Usando la stack del # 4 (demostrando la eliminación de la recursión de la cola)

version1 : Uso de progtwigción dinámica (tabulada – buscando con entusiasmo soluciones para todos los problemas de sum para llegar a la 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, 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-1] == w /// OR f(i-1, w) if weights[i-1] > w /// OR f(i-1, 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 (flojo, simplemente 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 stack (nota - misma complejidad - usando stack - eliminando recursividad de cola)

 public bool KnapsackIterativeUsingStack(int[] weights, int sum, out List knapsack) { sum.Throw("sum", s => s <= 0); weights.ThrowIfNull("weights"); weights.Throw("weights", w => (w.Length == 0) || w.Any(wi => wi < 0)); var knapsackIndices = new List(); knapsack = new List(); Stack stack = new Stack(); stack.Push(new KnapsackStackNode() { sumOfWeightsInTheKnapsack = 0, nextItemIndex = 1 }); stack.Push(new KnapsackStackNode() { sumOfWeightsInTheKnapsack = weights[0], nextItemIndex = 1, includesItemAtCurrentIndex = true }); knapsackIndices.Add(0); while(stack.Count > 0) { var top = stack.Peek(); if(top.sumOfWeightsInTheKnapsack == sum) { int count = 0; foreach(var index in knapsackIndices) { var w = weights[index]; knapsack.Add(w); count += w; } Debug.Assert(count == sum); return true; } //basically either of the below three cases, we dont need to traverse/explore adjuscent // nodes further if((top.nextItemIndex == weights.Length) //we reached end, no need to traverse || (top.sumOfWeightsInTheKnapsack > sum) // last added node should not be there || (top.alreadyExploredAdjuscentItems)) //already visted { if (top.includesItemAtCurrentIndex) { Debug.Assert(knapsackIndices.Contains(top.nextItemIndex - 1)); knapsackIndices.Remove(top.nextItemIndex - 1); } stack.Pop(); continue; } var node1 = new KnapsackStackNode(); node1.sumOfWeightsInTheKnapsack = top.sumOfWeightsInTheKnapsack; node1.nextItemIndex = top.nextItemIndex + 1; stack.Push(node1); var node2 = new KnapsackStackNode(); knapsackIndices.Add(top.nextItemIndex); node2.sumOfWeightsInTheKnapsack = top.sumOfWeightsInTheKnapsack + weights[top.nextItemIndex]; node2.nextItemIndex = top.nextItemIndex + 1; node2.includesItemAtCurrentIndex = true; stack.Push(node2); top.alreadyExploredAdjuscentItems = true; } return false; } 

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); } 

Aquí hay una implementación recursiva simple (no muy eficiente, pero fácil de seguir). Está en Python, OP está pidiendo una implementación de Java, pero portarlo a Java no debería ser demasiado difícil, es como mirar un pseudo-código.

La función principal declara tres parámetros: V es una matriz de valores, W es una matriz de pesos y C la capacidad de la mochila.

 def knapsack(V, W, C): return knapsack_aux(V, W, len(V)-1, C) def knapsack_aux(V, W, i, aW): if i == -1 or aW == 0: return 0 elif W[i] > aW: return knapsack_aux(V, W, i-1, aW) else: return max(knapsack_aux(V, W, i-1, aW), V[i] + knapsack_aux(V, W, i-1, aW-W[i])) 

El algoritmo maximiza el valor de los elementos agregados a la mochila, devolviendo el valor máximo alcanzable con los pesos dados

 public class Knapsack { public int[] arr = {11,8,7,6,5}; public int[] retArr = new int[5]; int i = 0; public boolean problem(int sum, int pick) { if(pick == arr.length) { return false; } if(arr[pick] < sum) { boolean r = problem(sum - arr[pick], pick+1); if(!r) { return problem(sum, pick+1); } else { retArr[i++] = arr[pick]; return true; } } else if (arr[pick] > sum) { return problem(sum, pick+1); } else { retArr[i++] = arr[pick]; return true; } } public static void main(String[] args) { Knapsack rk = new Knapsack`enter code here`(); if(rk.problem(20, 0)) { System.out.println("Success " ); for(int i=0; i < rk.retArr.length; i++) System.out.println(rk.retArr[i]); } } } 

Otra implementación de progtwigción dinámica en Java. Siempre me siento DP de arriba a abajo usando la memorización, es mucho más fácil de entender que el PD de abajo hacia arriba.

Código completo, autoexplicativo y ejecutable, usando datos de este ejemplo de Wikipedia :

 import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; public class Knapsack { private static final List ITEMS = new ArrayList<>(); private static final Map CACHE = new HashMap<>(); private static final boolean FINITE_ITEMS = true; //whether an item can be added more than once public static void main(String[] args) { ITEMS.add(new Item(4, 12, "GREEN")); ITEMS.add(new Item(2, 2, "CYAN")); ITEMS.add(new Item(2, 1, "GREY")); ITEMS.add(new Item(1, 1, "ORANGE")); ITEMS.add(new Item(10, 4, "YELLOW")); Bag best = bestBagForCapa(15); System.out.println(best.toString()); } public static Bag bestBagForCapa(int capa) { if (CACHE.containsKey(capa)) return CACHE.get(capa); if (capa < 0) return null; if (capa == 0) return new Bag(0, 0); int currentWeight = -1; int currentValue = -1; String newItem = null; List previousItems = null; for (Item p : ITEMS) { Bag previous = bestBagForCapa(capa - p.weight); if (previous == null) continue; int weightSoFar = previous.weight; int valueSoFar = previous.value; int nextBestValue = 0; Item candidateItem = null; for (Item candidate : ITEMS) { if (FINITE_ITEMS && previous.alreadyHas(candidate)) continue; if (weightSoFar + candidate.weight <= capa && nextBestValue < valueSoFar + candidate.value) { candidateItem = candidate; nextBestValue = valueSoFar + candidate.value; } } if (candidateItem != null && nextBestValue > currentValue) { currentValue = nextBestValue; currentWeight = weightSoFar + candidateItem.weight; newItem = candidateItem.name; previousItems = previous.contents; } } if (currentWeight <= 0 || currentValue <= 0) throw new RuntimeException("cannot be 0 here"); Bag bestBag = new Bag(currentWeight, currentValue); bestBag.add(previousItems); bestBag.add(Collections.singletonList(newItem)); CACHE.put(capa, bestBag); return bestBag; } } class Item { int value; int weight; String name; Item(int value, int weight, String name) { this.value = value; this.weight = weight; this.name = name; } } class Bag { List contents = new ArrayList<>(); int weight; int value; boolean alreadyHas(Item item) { return contents.contains(item.name); } @Override public String toString() { return "weight " + weight + " , value " + value + "\n" + contents.toString(); } void add(List name) { contents.addAll(name); } Bag(int weight, int value) { this.weight = weight; this.value = value; } } 

Aquí hay una solución Java

 static int knapsack(int[] values, int[] weights, int W, int[] tab, int i) { if(i>=values.length) return 0; if(tab[W] != 0) return tab[W]; int value1 = knapsack(values, weights, W, tab, i+1); int value2 = 0; if(W >= weights[i]) value2 = knapsack(values, weights, W-weights[i], tab, i+1) + values[i]; return tab[W] = (value1>value2) ? value1 : value2; } 

Pruébalo usando

 public static void main(String[] args) { int[] values = new int[] {894, 260, 392, 281, 27}; int[] weights = new int[] {8, 6, 4, 0, 21}; int W = 30; int[] tab = new int[W+1]; System.out.println(knapsack(values, weights, W, tab, 0)); } 

Aquí hay una solución recursiva simple en Java pero debe evitar el uso de la recursión si es posible.

 public class Knapsack { public static void main(String[] args) { int[] arr = new int[]{11, 8, 7, 6, 5}; find(arr,20); } public static boolean find( int[] arr,int total){ return find(arr,0,total); } private static boolean find( int[] arr,int start, int total){ if (start == arr.length){ return false; } int curr = arr[start]; if (curr == total){ System.out.println(curr); return true; }else if (curr > total || !find(arr,start+1,total-curr)){ return find(arr,start+1,total); } System.out.println(curr); return true; } }