Come posso risolvere l’algoritmo di zaino “classico” in modo ricorsivo?

Questo è il mio compito

The Knapsack Problem è un classico in informatica. Nella sua forma più semplice, consiste nel cercare di inserire oggetti di pesi diversi in uno zaino in modo che lo zaino finisca con un peso totale specificato. Non è necessario adattarsi a tutti gli articoli. Ad esempio, supponiamo di volere che lo zaino pesi esattamente 20 libbre e di avere cinque articoli, con pesi di 11, 8, 7, 6 e 5 libbre. Per un numero ridotto di oggetti, gli umani sono abbastanza bravi a risolvere questo problema con un’ispezione. Quindi puoi probabilmente capire che solo la combinazione 8, 7 e 5 di elementi aggiunge fino a 20.

Non so davvero da dove iniziare a scrivere questo algoritmo. Capisco la ricorsione quando applicata a fattoriali e numeri triangolari. Comunque mi sono perso adesso.

Cosa hai provato?

L’idea, dato il problema che hai dichiarato (che specifica che dobbiamo usare la ricorsione) è semplice: per ogni object che puoi prendere, vedi se è meglio prenderlo o meno. Quindi ci sono solo due possibili percorsi:

  1. prendi l’object
  2. non lo prendi

Quando prendi l’object, lo rimuovi dal tuo elenco e diminuisci la capacità in base al peso dell’object.

Quando non si prende l’object, si rimuove se dall’elenco ma non si diminuisce la capacità.

A volte aiuta a stampare come possono apparire le chiamate ricorsive. In questo caso, potrebbe assomigliare a questo:

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 

Ho fatto di proposito mostrare la chiamata a [8 7 6 5] con una capacità di 20, che dà un risultato di 20 (8 + 7 + 5).

Nota che [8 7 6 5] è chiamato due volte: una volta con una capacità di 20 (perché non abbiamo preso 11) e una volta con una capacità di 9 (perché con ha preso 11).

Quindi il percorso verso la soluzione:

11 non preso, chiamando [8 7 6 5] con una capacità di 20

8 presi, chiamando [7 6 5] con una capacità di 12 (20 – 8)

7 presi, chiamando [6 5] con una capacità di 5 (12 – 7)

6 non presi, chiamando [5] con una capacità di 5

5 presi, siamo a zero.

Il vero metodo in Java può adattarsi a poche righe di codice.

Dato che questo è ovviamente compito a casa, ti aiuterò solo con uno scheletro:

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

Ho copiato l'array in un nuovo array, che è meno efficiente (ma in ogni caso la ricorsione non è il modo di andare qui se cerchi prestazioni), ma più "funzionale".

Ho dovuto fare questo per i miei compiti quindi ho testato tutti i codici sopra (eccetto quello di Python), ma nessuno di essi funziona per ogni caso.

Questo è il mio codice, funziona per ogni caso.

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

Non è ottimizzato, la ricorsione ti ucciderà, ma puoi usare la semplice memoizzazione per risolverlo. Perché il mio codice è breve, corretto e comprensibile? Ho appena controllato la definizione matematica del problema dello Zaino 0-1 http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

Il problema è fondamentalmente la versione modificata del classico problema dello zaino per semplicità (non ci sono valori / benefici corrispondenti ai pesi) (per l’attuale: http://en.wikipedia.org/wiki/Knapsack_problem , 0/1 Zaino – Alcuni chiarimenti su Lo pseudocodice di Wiki , Come capire il problema dello zaino è NP-completo?, Perché il problema dello zaino è pseudo-polinomiale?, http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem / ).

Qui ci sono cinque versioni di risolvere questo in C #:

version1 : Uso della programmazione dynamic (tabulata – trovando con entusiasmo soluzioni per tutti i problemi di sum per arrivare a quella finale) – O (n * W)

versione 2 : Utilizzo di DP ma versione di memoization (pigro – solo trovare soluzioni per tutto ciò che è necessario)

versione 3 Utilizzo della ricorsione per dimostrare problemi secondari sovrapposti e sottostruttura ottimale

versione 4 Ricorsiva (forza bruta) – risposta sostanzialmente accettata

versione 5 Uso dello stack di # 4 (dimostrando di rimuovere la ricorsione della coda)

version1 : Uso della programmazione dynamic (tabulata – trovando con entusiasmo soluzioni per tutti i problemi di sum per arrivare a quella finale) – 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]; } 

versione 2 : Utilizzo di DP ma versione di memorizzazione (lazy – solo trovare soluzioni per tutto ciò che è necessario)

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

dove

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

versione 3 Identificazione dei sottotitoli sovrapposti e sottostruttura ottimale

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

dove

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

versione 4 Forza 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; } 

versione 5: versione iterativa usando stack (nota - stessa complessità - usando stack - rimuovendo la ricorsione della coda)

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

dove

 class KnapsackStackNode { public int sumOfWeightsInTheKnapsack; public int nextItemIndex; public bool alreadyExploredAdjuscentItems; public bool includesItemAtCurrentIndex; } 

E unit test

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

Ecco una semplice implementazione ricorsiva (non molto efficiente, ma facile da seguire). È in Python, OP sta chiedendo un’implementazione Java, ma portarlo su Java non dovrebbe essere troppo difficile, è come guardare lo pseudo-codice.

La funzione principale dichiara tre parametri: V è una matrice di valori, W è una matrice di pesi e C la capacità dello zaino.

 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])) 

L’algoritmo massimizza il valore degli elementi aggiunti allo zaino, restituendo il valore massimo raggiungibile con i pesi indicati

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

Ancora un’altra implementazione di programmazione dynamic in Java. Ho sempre sentito DP top-down usare la memoizzazione è molto più facile da capire rispetto al DP bottom-up.

Codice completo, autoesplicativo e eseguibile, utilizzando i dati di questo esempio da 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; } } 

Ecco una soluzione 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; } 

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

Ecco una semplice soluzione ricorsiva in Java ma dovresti evitare di ricorrere alla ricorsione se ansible.

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