मैं 'क्लासिक' knapsack एल्गोरिदम को पुनरावर्ती कैसे हल करूं?

Question

यह मेरा काम है

Knapsack समस्या कंप्यूटर विज्ञान में क्लासिक है। अपने सबसे सरल रूप में इसमें विभिन्न वजनों की वस्तुओं को knapsack में फिट करने का प्रयास करना शामिल है ताकि knapsack निर्दिष्ट कुल वजन के साथ समाप्त हो। आपको सभी वस्तुओं में फिट करने की आवश्यकता नहीं है। उदाहरण के लिए, मान लें कि आप अपने knapsack को केवल 20 पाउंड वजन करने के लिए चाहते हैं, और आपके पास 11, 8, 7, 6, और 5 पाउंड के वजन के साथ पांच आइटम, हैं। वस्तुओं की छोटी संख्या के लिए, इंसान निरीक्षण द्वारा इस समस्या को हल करने में बहुत अच्छे हैं। तो तुम शायद पता लगा सकते हैं कि वस्तुओं के केवल 8, 7, और 5 संयोजन 20.

अप करने के लिए कहते हैं मैं वास्तव में नहीं जानता कि जहां इस एल्गोरिथ्म लिखाई शुरू करने के। जब कारखानों और त्रिकोण संख्याओं पर लागू होता है तो मैं रिकर्सन को समझता हूं। हालांकि मैं अभी खो गया हूँ।

Answer 1

आप क्या प्रयास किया साथ?

आपके द्वारा बताई गई समस्या को देखते हुए विचार (जो निर्दिष्ट करता है कि हमें रिकर्सन का उपयोग करना चाहिए) सरल है: प्रत्येक आइटम जो आप ले सकते हैं, देखें कि यह लेना बेहतर है या नहीं। तो वहाँ केवल दो संभव पथ कर रहे हैं:

1. आप आइटम ले
2. आप नहीं लेते यह

जब आप आइटम ले, तो आप इसे अपनी सूची से हटा दें और आप क्षमता में कमी आइटम के वजन से।

जब आप आइटम नहीं लेते हैं, तो आप सूची से हटाते हैं लेकिन आप क्षमता कम नहीं करते हैं।

कभी-कभी यह प्रिंट करने में मदद करता है कि रिकर्सिव कॉल कैसा दिख सकता है। इस मामले में, यह ऐसा दिखाई दे सकता:

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 

मैंने जान-बूझकर 20 की क्षमता है, जिनमें से एक परिणाम देता है के साथ [8 7 6 5] को कॉल दिखाने की थी 20 (8 + 7 + 5) ।

ध्यान दें कि [8 7 6 5] दो बार बुलाया जाता है: एक बार 20 की क्षमता के साथ (क्योंकि हमने 11 नहीं लिया) और एक बार 9 की क्षमता के साथ (क्योंकि 11 ले लिया गया था)।

तो समाधान के लिए पथ:

11, नहीं लिया, [8 7 6 5] बुला 20

8 लिया की क्षमता के साथ बुला [7 6 5] 12 की क्षमता के साथ (20 - 8)

7 लिया, बुला [6 5] के 5 (12 क्षमता के साथ - 7)

6 से नहीं लिया, बुला [5] ले जाया 5

5 की क्षमता के साथ, हम शून्य पर हैं।

जावा में वास्तविक विधि कोड की बहुत कम पंक्तियों में फिट हो सकती है।

इस के बाद से स्पष्ट रूप से होमवर्क है, मैं सिर्फ एक कंकाल के साथ आपकी सहायता करेंगे:

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

मैं एक नई सरणी के सरणी कॉपी किया है, जो कम कुशल है (लेकिन वैसे भी प्रत्यावर्तन के लिए रास्ता नहीं है यदि आप प्रदर्शन चाहते हैं तो यहां जाएं), लेकिन अधिक "कार्यात्मक"।

Answer 2

यहां एक सरल पुनरावर्ती कार्यान्वयन है (बहुत कुशल नहीं है, लेकिन अनुसरण करने में आसान है)। यह पायथन में है, ओपी जावा कार्यान्वयन के लिए पूछ रहा है, लेकिन इसे जावा पर पोर्ट करना बहुत कठिन नहीं होना चाहिए, यह छद्म कोड को देखने जैसा है।

मुख्य कार्य तीन पैरामीटर घोषित करता है: वी मूल्यों की एक सरणी है, डब्ल्यू वजन की एक सरणी है और सी knapsack की क्षमता है।

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

एल्गोरिथ्म अधिकतम वस्तुओं के मूल्य नैपसैक को जोड़ा गया, अधिकतम मूल्य प्राप्य लौटने दिया वजन

Answer 3

यहाँ एक जावा समाधान

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

यह टेस्ट

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

का उपयोग करना है यहाँ जावा में एक सरल पुनरावर्ती समाधान है, लेकिन आप यदि संभव हो तो प्रत्यावर्तन का उपयोग कर से बचना चाहिए।

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

मैं तो मैं इसके बाद के संस्करण कोड (अजगर एक को छोड़कर) के सभी परीक्षण किया अपना होमवर्क के लिए यह करने के लिए किया था, लेकिन उनमें से कोई भी हर कोने मामले के लिए काम करते हैं।

यह मेरा कोड है, यह हर कोने के मामले के लिए काम करता है।

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

यह अनुकूलित नहीं है, रिकर्सन आपको मार देगा, लेकिन आप इसे ठीक करने के लिए सरल ज्ञापन का उपयोग कर सकते हैं। मेरा कोड छोटा, सही और समझने में आसान क्यों है? मैं सिर्फ 0-1 नेप्सेक समस्या 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

फिर भी जावा में एक और गतिशील प्रोग्रामिंग कार्यान्वयन की गणितीय परिभाषा की जाँच की। मुझे लगता है कि स्मोप का उपयोग करते हुए शीर्ष-डाउन डीपी नीचे डीपी की तुलना में समझना बहुत आसान है।

पूरा, आत्म व्याख्यात्मक, runnable कोड 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

समस्या मूल रूप से सादगी के लिए क्लासिक नेप्सेक समस्या के संस्करण संशोधित किया गया है (वहाँ कोई मान/लाभ हैं भार के अनुरूप) (वास्तविक के लिए: 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/)।(- सभी राशि की समस्याओं के लिए बेसब्री से खोजने समाधान द्वारा अंतिम एक को पाने के लिए सारणीबद्ध) - (n * डब्ल्यू) हे

गतिशील प्रोग्रामिंग का उपयोग करना:

version1:

यहाँ ग # में इस को हल करने के पांच संस्करण हैं

संस्करण 2: डीपी लेकिन Memoization संस्करण का उपयोग करना (आलसी - जो कुछ भी के लिए बस की खोज समाधान की जरूरत है)

संस्करण 3 प्रत्यावर्तन का उपयोग सु ओवरलैप प्रदर्शित करने के लिए ख समस्याओं और इष्टतम उप संरचना

संस्करण 4 रिकर्सिव (जानवर बल) - मूल रूप से स्वीकार किए जाते हैं जवाब

संस्करण 5 # 4 के ढेर का उपयोग करना (प्रदर्शन पूंछ प्रत्यावर्तन को हटाने)

version1: गतिशील प्रोग्रामिंग का उपयोग करना (सारणीबद्ध - सभी योग समस्याओं के लिए उत्सुकता से समाधान खोजने के लिए अंतिम रूप से प्राप्त करने के लिए) - ओ (एन * डब्ल्यू)

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

संस्करण 2: डीपी लेकिन याद संस्करण का उपयोग करना (आलसी - बस खोजने समाधान जो कुछ के लिए आवश्यक है)

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

जहां

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

संस्करण 3 ओवरलैप उप समस्याओं की पहचान करना और इष्टतम उप संरचना

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

जहां

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

संस्करण 4 ब्रूट बल

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

संस्करण 5: Iterative संस्करण ढेर का उपयोग कर (नोट - एक ही जटिलता - ढेर का उपयोग कर - हटाने के पूंछ प्रत्यावर्तन)

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

जहां

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

और इकाई परीक्षण

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