Come si risolve l'algoritmo di zaino "classico" in modo ricorsivo?

Question

Questo è il mio compito

lo zaino problema è un classico in informatica. Nella sua forma più semplice, , consiste nel cercare di inserire elementi di pesi diversi in uno zaino in modo che lo zaino finisca con un peso totale specificato. Non è necessario inserire tutti gli articoli. Ad esempio, supponiamo di volere lo zaino per pesare esattamente 20 sterline e di avere cinque articoli, con pesi di 11, 8, 7, 6 e 5 libbre. Per piccoli numeri di articoli, gli uomini sono abbastanza bravi a risolvere questo problema con un'ispezione. Così si può probabilmente capire che solo l'8, 7 e 5 combinazione di elementi aggiunge fino a 20.

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

Answer 1

Cosa hai provato?

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

1. si prende la voce
2. voi non lo porta

Quando si prende l'oggetto, si rimuove dalla vostra lista e si diminuisce la capacità dal peso dell'oggetto.

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

A volte è utile 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 apposta mostrano 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] viene 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 della soluzione:

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

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

7 prese, chiamando [6 5] con una capacità di 5; (12 - 7)

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

5 presa, siamo a zero.

Il metodo effettivo in Java può contenere pochissime righe di codice.

Dal momento che questo è ovviamente compiti a casa, mi limiterò a ti aiuti 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 a un nuovo array, che è meno efficiente (ma in ogni caso la ricorsione non è il modo per vai qui se cerchi prestazioni), ma più "funzionale".

Answer 2

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 è un array di valori, W è un array 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 alla bisaccia, restituendo il valore massimo raggiungibile con le indicazioni relative al peso

Answer 3

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

prove con il programma

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

Answer 4

Ecco una semplice soluzione ricorsiva in Java, ma si dovrebbe evitare di utilizzare la ricorsione, se possibile.

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

Answer 5

ho dovuto fare questo per il mio lavoro così ho provato tutti i codici di cui sopra (ad eccezione del Python uno), ma nessuno di loro lavoro per ogni caso angolo.

Questo è il mio codice, funziona per ogni caso angolare.

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

E non è ottimizzato, la ricorsione ti ucciderà, ma è possibile utilizzare semplice Memoizzazione per sistemare le cose. Perché il mio codice è breve, corretto e comprensibile? Ho appena controllato la definizione matematica del problema 0-1 zaino http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

Answer 6

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

} 

Answer 7

Ancora un'altra realizzazione programmazione dinamica in Java. Mi sento sempre DP top-down usare la memoizzazione è molto più facile da capire rispetto al DP bottom-up.

completa, auto-esplicativo, il codice eseguibile, utilizzando i dati di this example from 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<Item> ITEMS = new ArrayList<>(); 
    private static final Map<Integer, Bag> 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<String> 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<String> 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<String> name) { 
     contents.addAll(name); 
    } 

    Bag(int weight, int value) { 
     this.weight = weight; 
     this.value = value; 
    } 

} 

Answer 8

Il problema è fondamentalmente modificato la versione del classico problema dello zaino per semplicità (non ci sono valori/benefici corrispondente a pesi) (per l'attuale: http://en.wikipedia.org/wiki/Knapsack_problem, 0/1 Knapsack - A few clarification on Wiki's pseudocode, How to understand the knapsack problem is NP-complete?, Why is the knapsack problem pseudo-polynomial?, http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/).

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

version1: Utilizzo di programmazione dinamica (tabulati - da soluzioni ardentemente trovare per tutti i problemi di somma per arrivare a quella finale) - O (n * W)

versione 2: Usando DP ma la versione Memoizzazione (pigro - soluzioni solo trovare per tutto ciò che è necessario)

versione 3 utilizzando la ricorsione per dimostrare sovrapposti su b problemi e struttura sub ottimale

versione 4 Recursive (forza bruta) - risposta sostanzialmente accettato

versione 5 Uso pila di 4 # (dimostrando la rimozione coda ricorsione)

version1: Utilizzo della programmazione dinamica (tabulato - trovando con entusiasmo soluzioni per tutti i problemi di somma per arrivare a uno 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: Usando DP ma la versione memorizzazione (pigro - solo trovare soluzioni per tutto ciò che è necessario)

/// <summary> 
     /// 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]) 
     /// </summary> 
     /// <param name="rowIndexOfCache"> 
     /// Note, its index of row in the cache 
     /// index of given weifhts is indexOfCahce -1 (as it starts from 0) 
     /// </param> 
     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 Identificare i problemi secondari sovrapposti e sottostruttura ottimale

/// <summary> 
     /// 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]) 
     /// </summary> 
     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<int> 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<int> knapsack) 
     { 
      if(sum <= 0) 
      { 
       throw new ArgumentException("sum should be +ve non zero integer"); 
      } 
      knapsack = new List<int>(); 
      bool fits = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum: 0, index: 0, 
       itemsInTheKnapsack: knapsack); 
      return fits; 
     } 

versione 5: versione iterativa utilizzando pila (nota - stessa complessità - utilizzando stack - rimozione coda ricorsione)

public bool KnapsackIterativeUsingStack(int[] weights, int sum, out List<int> 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<int>(); 
      knapsack = new List<int>(); 
      Stack<KnapsackStackNode> stack = new Stack<KnapsackStackNode>(); 
      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<int> 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); 
     }