/* A Naive recursive implementation of  0-1 Knapsack problem */ #include  using namespace std; // A utility function that returns // maximum of two integers int max(int a, int b) { return (a>B) ? a : b; } // Gibt den Maximalwert zurück, der // in einen Rucksack mit Kapazität gesteckt werden kann W int knapSack(int W, int wt[], int val[], int n) // Basisfall if (n == 0 // Treibercode int main() { int profit[] = { 60, 100, 120 }; int Weight[] = { 10, 20, 30 }; 0]); cout<< knapSack(W, weight, profit, n);  return 0; } // This code is contributed by rathbhupendra>

/* A Naive recursive implementation of 0-1 Knapsack problem */ #include  // A utility function that returns // maximum of two integers int max(int a, int b) { return (a>B) ? a : b; } // Gibt den Maximalwert zurück, der // in einen Rucksack mit Kapazität gesteckt werden kann W int knapSack(int W, int wt[], int val[], int n) W == 0) return 0;  // Wenn das Gewicht des n-ten Elements mehr als // Rucksackkapazität W beträgt, kann dieses Element // nicht in die optimale Lösung einbezogen werden, wenn (wt[n - 1]> W) return knapSack(W, wt, val, n - 1);  // Das Maximum von zwei Fällen zurückgeben: // (1) n-tes Element enthalten // (2) nicht enthalten else return max( val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));  // Treibercode int main() { int profit[] = { 60, 100, 120 };  int Gewicht[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  printf('%d', knapSack(W, Weight, Profit, n));  0 zurückgeben; }>

/* A Naive recursive implementation of 0-1 Knapsack problem */ class Knapsack {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>B) ? a : b; } // Gibt den Maximalwert zurück, der // in einen Rucksack mit // Kapazität gesteckt werden kann W static int knapSack(int W, int wt[], int val[], int n) // Treibercode public static void main( String args[]) { int profit[] = new int[] { 60, 100, 120 };  int Weight[] = new int[] { 10, 20, 30 };  int W = 50;  int n = profit.length;  System.out.println(knapSack(W, Weight, Profit, n));  } } /*Dieser Code wurde von Rajat Mishra beigesteuert */>

# A naive recursive implementation # of 0-1 Knapsack Problem # Returns the maximum value that # can be put in a knapsack of # capacity W def knapSack(W, wt, val, n): # Base Case if n == 0 or W == 0: return 0 # If weight of the nth item is # more than Knapsack of capacity W, # then this item cannot be included # in the optimal solution if (wt[n-1]>W): return knapSack(W, wt, val, n-1) # das Maximum von zwei Fällen zurückgeben: # (1) n-tes Element enthalten # (2) nicht enthalten else: return max( val[n-1] + knapSack ( W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # Ende der Funktion knapSack # Treibercode, wenn __name__ == '__main__': profit = [60, 100, 120] Weight = [10, 20, 30] W = 50 n = len(profit) print knapSack(W, Weight, profit, n) # Dieser Code wurde von Nikhil Kumar Singh beigesteuert>

/* A Naive recursive implementation of 0-1 Knapsack problem */ using System; class GFG {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>B) ? a : b; } // Gibt den Maximalwert zurück, der // in einen Rucksack mit Kapazität W gesteckt werden kann static int knapSack(int W, int[] wt, int[] val, int n) W == 0) return 0;  // Wenn das Gewicht des n-ten Elements // größer als die Rucksackkapazität W ist, // kann dieses Element nicht // in die optimale Lösung einbezogen werden, wenn (wt[n - 1]> W) return knapSack(W, wt, val , n - 1);  // Das Maximum von zwei Fällen zurückgeben: // (1) n-tes Element enthalten // (2) nicht enthalten else return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));    // Treibercode public static void Main() { int[] profit = new int[] { 60, 100, 120 };  int[] Weight = new int[] { 10, 20, 30 };  int W = 50;  int n = profit.Length;  Console.WriteLine(knapSack(W, Weight, Profit, n));  } } // Dieser Code wurde von Sam007 beigesteuert>

 /* A Naive recursive implementation of  0-1 Knapsack problem */    // A utility function that returns  // maximum of two integers  function max(a, b)  {  return (a>B) ? a : b;  } // Gibt den Maximalwert zurück, der // in einen Rucksack mit Kapazität gesteckt werden kann W function knapSack(W, wt, val, n) // Basisfall if (n == 0 let profit = [ 60, 100, 120 ] ; let Weight = [ 10, 20, 30 ]; let W = 50; let n = profit.length(knapSack(W, Weight, n));PHP220>

Zeitkomplexität: O(2^N)
Hilfsraum: O(N), für die Rekursion erforderlicher Stapelplatz

Dynamischer Programmieransatz für das 0/1-Rucksackproblem

Memoisierungsansatz für das 0/1-Rucksackproblem:

Notiz: Es ist zu beachten, dass die obige Funktion mithilfe der Rekursion immer wieder dieselben Teilprobleme berechnet. Siehe den folgenden Rekursionsbaum: K(1, 1) wird zweimal ausgewertet.

Im folgenden Rekursionsbaum K() bezieht sich auf knapSack(). Die beiden im folgenden Rekursionsbaum angegebenen Parameter sind n und W.
Der Rekursionsbaum dient für die folgenden Beispieleingaben.
Gewicht[] = {1, 1, 1}, W = 2, Gewinn[] = {10, 20, 30}

K(3, 2)
/
/
K(2, 2) K(2, 1)
/ /
/ /
K(1, 2) K(1, 1) K(1, 1) K(1, 0)
/ / /
/ / /
K(0, 2) K(0, 1) K(0, 1) K(0, 0) K(0, 1) K(0, 0)

Rekursionsbaum für Rucksackkapazität 2 Einheiten und 3 Artikel mit 1 Einheit Gewicht.

Da es immer wieder Wiederholungen desselben Teilproblems gibt, können wir die folgende Idee zur Lösung des Problems umsetzen.

Wenn wir zum ersten Mal ein Teilproblem haben, können wir dieses Problem lösen, indem wir ein 2D-Array erstellen, das einen bestimmten Zustand (n, w) speichern kann. Wenn wir nun erneut auf denselben Zustand (n, w) stoßen, anstatt ihn in exponentieller Komplexität zu berechnen, können wir sein in der Tabelle gespeichertes Ergebnis direkt in konstanter Zeit zurückgeben.

String-Array

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

// Here is the top-down approach of // dynamic programming #include  using namespace std; // Returns the value of maximum profit int knapSackRec(int W, int wt[], int val[], int index, int** dp) {  // base condition  if (index < 0)  return 0;  if (dp[index][W] != -1)  return dp[index][W];  if (wt[index]>W) { // Den Wert des Funktionsaufrufs // vor der Rückgabe in der Tabelle speichern dp[index][W] = knapSackRec(W, wt, val, index - 1, dp);  return dp[index][W];  } else { // Wert vor Rückgabe in einer Tabelle speichern dp[index][W] = max(val[index] + knapSackRec(W - wt[index], wt, val, index - 1, dp), knapSackRec(W , wt, val, index - 1, dp));  // Rückgabewert der Tabelle nach dem Speichern return dp[index][W];  } } int knapSack(int W, int wt[], int val[], int n) { // Doppelzeiger zum dynamischen Deklarieren der // Tabelle int** dp;  dp = new int*[n];  // Schleife zum dynamischen Erstellen der Tabelle für (int i = 0; i< n; i++)  dp[i] = new int[W + 1];  // loop to initially filled the  // table with -1  for (int i = 0; i < n; i++)  for (int j = 0; j < W + 1; j++)  dp[i][j] = -1;  return knapSackRec(W, wt, val, n - 1, dp); } // Driver Code int main() {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  cout << knapSack(W, weight, profit, n);  return 0; }>

// Here is the top-down approach of // dynamic programming import java.io.*; class GFG {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>B) ? a : b; } // Gibt den Wert des maximalen Gewinns zurück static int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) W == 0) return 0;  if (dp[n][W] != -1) return dp[n][W];  if (wt[n - 1]> W) // Wert des Funktionsaufrufs speichern // vor der Rückgabe in der Tabelle stapeln return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);  else // Rückgabewert der Tabelle nach dem Speichern return dp[n][W] = max((val[n - 1] + knapSackRec(W - wt[n - 1], wt, val, n - 1, dp)) , knapSackRec(W, wt, val, n - 1, dp));    static int knapSack(int W, int wt[], int val[], int N) { // Tabelle dynamisch deklarieren int dp[][] = new int[N + 1][W + 1];  // Schleife, um die // Tabelle anfänglich mit -1 zu füllen for (int i = 0; i< N + 1; i++)  for (int j = 0; j < W + 1; j++)  dp[i][j] = -1;  return knapSackRec(W, wt, val, N, dp);  }  // Driver Code  public static void main(String[] args)  {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int N = profit.length;  System.out.println(knapSack(W, weight, profit, N));  } } // This Code is contributed By FARAZ AHMAD>

# This is the memoization approach of # 0 / 1 Knapsack in Python in simple # we can say recursion + memoization = DP def knapsack(wt, val, W, n): # base conditions if n == 0 or W == 0: return 0 if t[n][W] != -1: return t[n][W] # choice diagram code if wt[n-1] <= W: t[n][W] = max( val[n-1] + knapsack( wt, val, W-wt[n-1], n-1), knapsack(wt, val, W, n-1)) return t[n][W] elif wt[n-1]>W: t[n][W] = knapsack(wt, val, W, n-1) return t[n][W] # Treibercode if __name__ == '__main__': profit = [60, 100, 120] Gewicht = [10, 20, 30] W = 50 n = len(profit) # Wir initialisieren die Matrix zunächst mit -1. t = [[-1 für i im Bereich (W + 1)] für j im Bereich (n + 1)] print(knapsack(weight, profit, W, n)) # Dieser Code wurde von Prosun Kumar Sarkar beigesteuert>'>C# 
// A utility function that returns // maximum of two integers  function max(a, b)  {   return (a>B) ? a : b;  } // Gibt den Wert des maximalen Gewinns zurück function knapSackRec(W, wt, val, n,dp) // Basisbedingung if (n == 0 function knapSack( W, wt,val,N) { // Deklarieren Sie die dp-Tabelle dynamisch // DP-Tabellen (Zeilen und Spalten) mit -1 unten initialisieren var dp = new Array(N+1).fill(-1).map(el => new Array(W+1).fill(-1) ); return knapSackRec(W, wt, val, N, dp); var profit= [ 10, 20, 30 ]; var N = profit.length ; console.log(knapSack(W, Weight, Profit, N)); // Dieser Code wurde von akshitsaxenaa09 beigesteuert  
  Ausgabe  
220>
  
    Zeitkomplexität:    O(N * W). Dadurch werden redundante Zustandsberechnungen vermieden.  
    Hilfsraum:    O(N * W) + O(N). Für den Rekursionsstapel wurde eine 2D-Array-Datenstruktur zum Speichern von Zwischenzuständen und O(N) Auxiliary Stack Space (ASS) verwendet
 
    Bottom-up-Ansatz für das 0/1-Rucksackproblem:    
Um das Problem zu lösen, befolgen Sie die folgende Idee:
  
Da Teilprobleme erneut ausgewertet werden, verfügt dieses Problem über die Eigenschaft „Überlappende Teilprobleme“. Das 0/1-Knapsack-Problem hat also beide Eigenschaften (siehe Das Und Das ) eines dynamischen Programmierproblems. Wie andere typische Probleme mit der dynamischen Programmierung (DP). , kann eine erneute Berechnung derselben Teilprobleme vermieden werden, indem ein temporäres Array K[][] von unten nach oben erstellt wird.
 
    Illustration:    
 
Nachfolgend finden Sie eine Darstellung des oben genannten Ansatzes:
  
Lassen,    Gewicht[] = {1, 2, 3}, Gewinn[] = {10, 15, 40}, Kapazität = 6    
 
Wenn kein Element gefüllt ist, beträgt der mögliche Gewinn 0.
Gewicht⇢  
Artikel⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
 
 
 
 
 
 
 
2
 
 
 
 
 
 
 
3
 
 
 
 
 
 
 
    Zum Befüllen des ersten Artikels im Beutel:    Wenn wir dem oben beschriebenen Verfahren folgen, sieht die Tabelle wie folgt aus.
Gewicht⇢  
Artikel⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
0
10
10
10
10
10
10
2
 
 
 
 
 
 
 
3
 
 
 
 
 
 
 
    Zum Ausfüllen des zweiten Elements:       
Wenn jthWeight = 2, beträgt der maximal mögliche Gewinn max (10, DP[1][2-2] + 15) = max(10, 15) = 15.  
Wenn jthWeight = 3, dann beträgt der maximal mögliche Gewinn max(2 nicht gelegt, 2 wird in den Beutel gelegt) = max(DP[1][3], 15+DP[1][3-2]) = max(10, 25) = 25.
Gewicht⇢  
Artikel⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
0
10
10
10
10
10
10
2
0
10
fünfzehn
25
25
25
25
3
 
 
 
 
 
 
 
    Zum Ausfüllen des dritten Elements:     
Wenn jthWeight = 3, beträgt der maximal mögliche Gewinn max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.  
Wenn jthWeight = 4, beträgt der maximal mögliche Gewinn max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.  
Wenn jthWeight = 5, beträgt der maximal mögliche Gewinn max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.  
Wenn jthWeight = 6, beträgt der maximal mögliche Gewinn max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
Gewicht⇢  
Artikel⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
0
10
10
10
10
10
10
2
0
10
fünfzehn
25
25
25
25
3
0
10
fünfzehn
40
fünfzig
55
65
Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:
C++ 
// A dynamic programming based // solution for 0-1 Knapsack problem #include  using namespace std; // A utility function that returns // maximum of two integers int max(int a, int b) { return (a>B) ? a : b; } // Gibt den Maximalwert zurück, der // in einen Rucksack mit Kapazität gesteckt werden kann W int knapSack(int W, int wt[], int val[], int n) { int i, w;  Vektor> K(n + 1, Vektor (W + 1));  // Tabelle K[][] von unten nach oben erstellen für (i = 0; i<= n; i++) {  for (w = 0; w <= W; w++)   if (i == 0   }  return K[n][W]; } // Driver Code int main() {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  cout << knapSack(W, weight, profit, n);  return 0; } // This code is contributed by Debojyoti Mandal>
 C 
// A Dynamic Programming based // solution for 0-1 Knapsack problem #include  // A utility function that returns // maximum of two integers int max(int a, int b) { return (a>B) ? a : b; } // Gibt den Maximalwert zurück, der // in einen Rucksack mit Kapazität gesteckt werden kann W int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[n + 1][W + 1];  // Tabelle K[][] von unten nach oben erstellen für (i = 0; i<= n; i++) {  for (w = 0; w <= W; w++)   if (i == 0   }  return K[n][W]; } // Driver Code int main() {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  printf('%d', knapSack(W, weight, profit, n));  return 0; }>
 Java 
// A Dynamic Programming based solution // for 0-1 Knapsack problem import java.io.*; class Knapsack {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>B) ? a : b; } // Gibt den Maximalwert zurück, der // in einen Rucksack mit der Kapazität W gesteckt werden kann static int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[][] = new int[n + 1][W + 1];  // Tabelle K[][] von unten nach oben erstellen für (i = 0; i<= n; i++) {  for (w = 0; w <= W; w++)   if (i == 0   }  return K[n][W];  }  // Driver code  public static void main(String args[])  {  int profit[] = new int[] { 60, 100, 120 };  int weight[] = new int[] { 10, 20, 30 };  int W = 50;  int n = profit.length;  System.out.println(knapSack(W, weight, profit, n));  } } /*This code is contributed by Rajat Mishra */>
 Python 
# A Dynamic Programming based Python # Program for 0-1 Knapsack problem # Returns the maximum value that can # be put in a knapsack of capacity W def knapSack(W, wt, val, n): K = [[0 for x in range(W + 1)] for x in range(n + 1)] # Build table K[][] in bottom up manner for i in range(n + 1): for w in range(W + 1): if i == 0 or w == 0: K[i][w] = 0 elif wt[i-1] <= w: K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) else: K[i][w] = K[i-1][w] return K[n][W] # Driver code if __name__ == '__main__': profit = [60, 100, 120] weight = [10, 20, 30] W = 50 n = len(profit) print(knapSack(W, weight, profit, n)) # This code is contributed by Bhavya Jain>
 C# 
// A Dynamic Programming based solution for // 0-1 Knapsack problem using System; class GFG {  // A utility function that returns  // maximum of two integers  static int max(int a, int b) { return (a>B) ? a : b; } // Gibt den Maximalwert zurück, der // in einen Rucksack mit // Kapazität W gepackt werden kann static int knapSack(int W, int[] wt, int[] val, int n) { int i, w;  int[, ] K = new int[n + 1, W + 1];  // Tabelle K[][] von unten // nach oben erstellen für (i = 0; i<= n; i++) {  for (w = 0; w <= W; w++)   }  return K[n, W];  }  // Driver code  static void Main()  {  int[] profit = new int[] { 60, 100, 120 };  int[] weight = new int[] { 10, 20, 30 };  int W = 50;  int n = profit.Length;  Console.WriteLine(knapSack(W, weight, profit, n));  } } // This code is contributed by Sam007>
 Javascript 
 // A Dynamic Programming based solution  // for 0-1 Knapsack problem    // A utility function that returns  // maximum of two integers  function max(a, b)  {  return (a>B) ? a : b;  } // Gibt den Maximalwert zurück, der // in einen Rucksack mit Kapazität gesteckt werden kann W function knapSack(W, wt, val, n) { let i, w;  sei K = new Array(n + 1);    // Tabelle K[][] von unten nach oben erstellen für (i = 0; i<= n; i++)  {  K[i] = new Array(W + 1);  for (w = 0; w <= W; w++)   w == 0)  K[i][w] = 0;  else if (wt[i - 1] <= w)  K[i][w]  = max(val[i - 1]  + K[i - 1][w - wt[i - 1]],  K[i - 1][w]);  else  K[i][w] = K[i - 1][w];    }    return K[n][W];  }    let profit = [ 60, 100, 120 ];  let weight = [ 10, 20, 30 ];  let W = 50;  let n = profit.length;  console.log(knapSack(W, weight, profit, n));>
 PHP 
 // A Dynamic Programming based solution // for 0-1 Knapsack problem // Returns the maximum value that // can be put in a knapsack of  // capacity W function knapSack($W, $wt, $val, $n) { $K = array(array()); // Build table K[][] in // bottom up manner for ($i = 0; $i <= $n; $i++) { for ($w = 0; $w <= $W; $w++)  } return $K[$n][$W]; } // Driver Code $profit = array(60, 100, 120); $weight = array(10, 20, 30); $W = 50; $n = count($profit); echo knapSack($W, $weight, $profit, $n); // This code is contributed by Sam007. ?>>
   
  Ausgabe      Zeitkomplexität:    O(N * W). Dabei ist „N“ die Anzahl der Elemente und „W“ die Kapazität.  
    Hilfsraum:    O(N * W). Die Verwendung eines 2D-Arrays der Größe „N*W“.
Ausnahmebehandlung Java
 
    Platzoptimierter Ansatz für das 0/1-Rucksackproblem unter Verwendung dynamischer Programmierung:    
Um das Problem zu lösen, befolgen Sie die folgende Idee:
  
Für die Berechnung der aktuellen Zeile des dp[]-Arrays benötigen wir nur die vorherige Zeile. Wenn wir jedoch beginnen, die Zeilen von rechts nach links zu durchlaufen, kann dies nur mit einer einzelnen Zeile erfolgen
 
Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:
C++ 
// C++ program for the above approach #include  using namespace std; // Function to find the maximum profit int knapSack(int W, int wt[], int val[], int n) {  // Making and initializing dp array  int dp[W + 1];  memset(dp, 0, sizeof(dp));  for (int i = 1; i < n + 1; i++) {  for (int w = W; w>= 0; w--) { if (wt[i - 1]<= w)    // Finding the maximum value  dp[w] = max(dp[w],  dp[w - wt[i - 1]] + val[i - 1]);  }  }  // Returning the maximum value of knapsack  return dp[W]; } // Driver code int main() {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  cout << knapSack(W, weight, profit, n);  return 0; }>
 Java 
// Java program for the above approach import java.util.*; class GFG {  static int knapSack(int W, int wt[], int val[], int n)  {  // Making and initializing dp array  int[] dp = new int[W + 1];  for (int i = 1; i < n + 1; i++) {  for (int w = W; w>= 0; w--) { if (wt[i - 1]<= w)  // Finding the maximum value  dp[w]  = Math.max(dp[w], dp[w - wt[i - 1]]  + val[i - 1]);  }  }  // Returning the maximum value of knapsack  return dp[W];  }  // Driver code  public static void main(String[] args)  {  int profit[] = { 60, 100, 120 };  int weight[] = { 10, 20, 30 };  int W = 50;  int n = profit.length;  System.out.print(knapSack(W, weight, profit, n));  } } // This code is contributed by gauravrajput1>
 Python 
# Python code to implement the above approach def knapSack(W, wt, val, n): # Making the dp array dp = [0 for i in range(W+1)] # Taking first i elements for i in range(1, n+1): # Starting from back, # so that we also have data of # previous computation when taking i-1 items for w in range(W, 0, -1): if wt[i-1] <= w: # Finding the maximum value dp[w] = max(dp[w], dp[w-wt[i-1]]+val[i-1]) # Returning the maximum value of knapsack return dp[W] # Driver code if __name__ == '__main__': profit = [60, 100, 120] weight = [10, 20, 30] W = 50 n = len(profit) print(knapSack(W, weight, profit, n)) # This code is contributed by Suyash Saxena>
 C# 
// Java program for the above approach using System; public class GFG {  static int knapSack(int W, int[] wt, int[] val, int n)  {  // Making and initializing dp array  int[] dp = new int[W + 1];  for (int i = 1; i < n + 1; i++) {  for (int w = W; w>= 0; w--) { if (wt[i - 1]<= w)  // Finding the maximum value  dp[w]  = Math.Max(dp[w], dp[w - wt[i - 1]]  + val[i - 1]);  }  }  // Returning the maximum value of knapsack  return dp[W];  }  // Driver code  public static void Main(String[] args)  {  int[] profit = { 60, 100, 120 };  int[] weight = { 10, 20, 30 };  int W = 50;  int n = profit.Length;  Console.Write(knapSack(W, weight, profit, n));  } } // This code is contributed by gauravrajput1>
 Javascript 
 function knapSack(W , wt , val , n)  {  // Making and initializing dp array  var dp = Array(W + 1).fill(0);  for (i = 1; i < n + 1; i++) {  for (w = W; w>= 0; w--) { if (wt[i - 1]<= w)  // Finding the maximum value  dp[w] = Math.max(dp[w], dp[w - wt[i - 1]] + val[i - 1]);  }  }    // Returning the maximum value of knapsack  return dp[W];  }  // Driver code  var profit = [ 60, 100, 120 ];  var weight = [ 10, 20, 30 ];  var W = 50;  var n = profit.length;  console.log(knapSack(W, weight, profit, n)); // This code is contributed by Rajput-Ji>
   
  Ausgabe  
220>
 
    Zeitkomplexität    : O(N * W). Dadurch werden redundante Zustandsberechnungen vermieden  
    Hilfsraum    : O(W) Da wir ein 1-D-Array anstelle eines 2-D-Arrays verwenden