Requisits previs: Introducció al problema de la motxilla, els seus tipus i com resoldre'ls

Donat N articles on cada article té algun pes i benefici associat i també se'ls dóna una bossa amb capacitat EN , [és a dir, la bossa pot contenir com a màxim EN pes en ella]. La tasca és posar els articles a la bossa de manera que la suma dels beneficis associats sigui el màxim possible.

Nota: La limitació aquí és que podem posar un article completament a la bossa o no podem posar-lo en absolut [No és possible posar una part d'un article a la bossa].

Exemples:

Entrada: N = 3, W = 4, benefici[] = {1, 2, 3}, pes[] = {4, 5, 1}
Sortida: 3
Explicació: Hi ha dos articles que tenen un pes inferior o igual a 4. Si seleccionem l'article amb pes 4, el benefici possible és 1. I si seleccionem l'article amb pes 1, el benefici possible és 3. Per tant, el benefici màxim possible és 3. Tingueu en compte que no podem unir els dos articles amb pes 4 i 1, ja que la capacitat de la bossa és de 4.

Entrada: N = 3, W = 3, benefici[] = {1, 2, 3}, pes[] = {4, 5, 6}
Sortida: 0

Enfocament de recursivitat per al problema de la motxilla 0/1:

Per resoldre el problema seguiu la idea següent:

Una solució senzilla és considerar tots els subconjunts d'articles i calcular el pes total i el benefici de tots els subconjunts. Considereu els únics subconjunts el pes total dels quals és menor que W. De tots aquests subconjunts, trieu el subconjunt amb el màxim benefici.

mysql canvia el tipus de columna

Subestructura òptima : Per considerar tots els subconjunts d'elements, hi pot haver dos casos per a cada element.

• Cas 1: L'element s'inclou al subconjunt òptim.
• Cas 2: L'article no està inclòs en el conjunt òptim.

Seguiu els passos següents per resoldre el problema:

El valor màxim obtingut de 'N' elements és el màxim dels dos valors següents.

• Cas 1 (inclou el N^thítem): valor de la N^thítem més el valor màxim obtingut pels elements N-1 restants i el pes restant, és a dir (pes W del N^tharticle).
• Cas 2 (exclou el N^thítem): Valor màxim obtingut per N-1 articles i pes W.
• Si el pes de la ‘N^th'l'element és més gran que 'W', aleshores no es pot incloure l'element N i Cas 2 és l'única possibilitat.

A continuació es mostra la implementació de l'enfocament anterior:

/* 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; } // Retorna el valor màxim que // es pot posar en una motxilla de capacitat W int knapSack(int W, int wt[], int val[], int n) // Cas base si (n == 0 // Codi del controlador int main() { int profit[] = { 60, 100, 120 } int weight [] = { 10, 20, 30 } int W = 50 (profit) / sizeof (profit); 0]);<< 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; } // Retorna el valor màxim que es pot // posar en una motxilla de capacitat W int knapSack(int W, int wt[], int val[], int n) W == 0) return 0;  // Si el pes de l'nè ítem és superior a // la capacitat de la motxilla W, aleshores aquest element no es pot // incloure a la solució òptima si (wt[n - 1]> W) retorna knapSack(W, wt, val, n - 1);  // Retorna el màxim de dos casos: // (1) nè ítem inclòs // (2) no inclòs sinó retorna max( val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), motxilla (W, wt, val, n - 1));  // Codi del controlador int main() { int profit[] = { 60, 100, 120 };  pes int[] = {10, 20, 30};  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  printf('%d', motxilla(W, pes, benefici, n));  retorn 0; }>>>Java 
# 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): retorna knapSack(W, wt, val, n-1) # retorna el màxim de dos casos: # (1) nè ítem inclòs # (2) no inclòs sinó: return max( val[n-1] + knapSack (W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # final de la funció knapSack # Codi del controlador si __name__ == '__main__': benefici = [60, 100, 120] pes = [10, 20, 30] W = 50 n = len(profit) imprimir motxilla (W, pes, benefici, n) # Aquest codi és aportat per Nikhil Kumar Singh>
 C# 
/* 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; } // Retorna el valor màxim que es pot // posar en una motxilla de capacitat W static int knapSack(int W, int[] wt, int[] val, int n) W == 0) return 0;  // Si el pes de l'enèsim article és // més que la capacitat de la motxilla W, // llavors aquest article no es pot // incloure a la solució òptima si (wt[n - 1]> W) retorna la motxilla (W, wt, val , n - 1);  // Retorna el màxim de dos casos: // (1) nè ítem inclòs // (2) no inclòs sinó retorna max(val[n - 1] + motxilla(W - pes[n - 1], pes, val, n - 1), motxilla (W, wt, val, n - 1));    // Codi del controlador public static void Main() { int[] profit = new int[] { 60, 100, 120 };  int[] pes = nou int[] {10, 20, 30};  int W = 50;  int n = benefici.Longitud;  Console.WriteLine(knapSack(W, pes, benefici, n));  } } // Aquest codi és aportat per Sam007>>>Javascript$W) torna motxilla($W, $wt, $val, $n - 1); // Retorna el màxim de dos casos: // (1) nè element inclòs // (2) no inclòs sinó retorna max($val[$n - 1] + knapSack($W - $wt[$n - 1] , $wt, $val, $n - 1), motxilla ($W, $wt, $val, $n-1));  // Codi del controlador $profit = array(60, 100, 120); $pes = matriu (10, 20, 30); $W = 50; $n = comptar ($benefici); echo knapSack($W, $pes, $benefici, $n); // Aquest codi és aportat per Sam007 ?>>
   
  Sortida  
220>
 
    Complexitat temporal:    O (2N)  
    Espai auxiliar:    O(N), espai de pila necessari per a la recursivitat
 
Enfocament de programació dinàmica per al problema de la motxilla 0/1
Enfocament de memorització per al problema de la motxilla 0/1:
    Nota:    Cal tenir en compte que la funció anterior utilitzant recursivitat calcula els mateixos subproblemes una i altra vegada. Vegeu el següent arbre de recursivitat, K(1, 1) s'està avaluant dues vegades.
  
En el següent arbre de recursivitat,    K()    fa referència a knapSack(). Els dos paràmetres indicats a l'arbre de recursivitat següent són n i W.  
L'arbre de recursivitat és per a les entrades de mostra següents.  
pes[] = {1, 1, 1}, W = 2, benefici[] = {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)
 
Arbre de recursivitat per motxilla de capacitat 2 unitats i 3 articles d'1 unitat de pes.
 
Com que hi ha repeticions del mateix subproblema una i altra vegada podem implementar la següent idea per resoldre el problema.
  
Si obtenim un subproblema la primera vegada, podem resoldre aquest problema creant una matriu 2-D que pugui emmagatzemar un estat particular (n, w). Ara, si tornem a trobar el mateix estat (n, w) en lloc de calcular-lo en complexitat exponencial, podem retornar directament el seu resultat emmagatzemat a la taula en temps constant.
trencar java
 
A continuació es mostra la implementació de l'enfocament anterior:
C++ 
// 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) { // Emmagatzema el valor de la crida de funció // apila a la taula abans de retornar dp[índex][W] = knapSackRec(W, wt, val, index - 1, dp);  retornar dp[índex][W];  } else { // Emmagatzema el valor en una taula abans de retornar dp[índex][W] = max(val[índex] + knapSackRec(W - wt[índex], wt, val, index - 1, dp), knapSackRec(W , pes, val, índex - 1, dp));  // Retorna el valor de la taula després d'emmagatzemar return dp[índex][W];  } } int knapSack(int W, int wt[], int val[], int n) { // punter doble per declarar // la taula dinàmicament int** dp;  dp = nou int*[n];  // bucle per crear la taula dinàmicament per (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; }>
 Java 
// 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; } // Retorna el valor del benefici màxim estàtic int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) W == 0) return 0;  si (dp[n][W] != -1) retorna dp[n][W];  if (wt[n - 1]> W) // Emmagatzema el valor de la trucada de funció // apila a la taula abans de retornar return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);  else // Retorna el valor de la taula després d'emmagatzemar el retorn 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) { // Declara la taula dinàmicament int dp[][] = new int[N + 1][W + 1];  // Bucle per omplir inicialment la // taula amb -1 per (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>
 Python 
# 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] = motxilla(wt, val, W, n-1) retorna t[n][W] # Codi del conductor si __name__ == '__main__': benefici = [60, 100, 120] pes = [10, 20, 30] W = 50 n = len(profit) # Inicialitzem la matriu amb -1 al principi. t = [[-1 per a i en el rang (W + 1)] per a j en el rang (n + 1)] print(motxilla (pes, benefici, W, n)) # Aquest codi és aportat per Prosun Kumar Sarkar>'>C# 
// A utility function that returns // maximum of two integers  function max(a, b)  {   return (a>b)? a: b;  } // Retorna el valor de la funció de benefici màxim knapSackRec(W, wt, val, n,dp) // Condició base si (n == 0 funció knapSack(W, wt,val,N) { // Declara la taula dp dinàmicament // Inicialització de taules dp (fila i cols) amb -1 per sota var dp = new Array(N+1).fill(-1).map(el => new Array(W+1).fill(-1) ); retorn knapSackRec(W, wt, val, N, dp } var profit= [ 60, 100, 120 ] var W = 50; ; console.log(knapSack(W, weight, profit, N) // Aquest codi és aportat per akshitsaxenaa09  
  Sortida  
220>
  
    Complexitat temporal:    O (N * W). Com s'eviten els càlculs redundants d'estats.  
    Espai auxiliar:    O(N * W) + O(N). S'ha utilitzat l'ús d'una estructura de dades de matriu 2D per emmagatzemar estats intermedis i espai de pila auxiliar (ASS) O(N) per a la pila de recursivitat
 
    Enfocament de baix a dalt per al problema de la motxilla 0/1:    
Per resoldre el problema seguiu la idea següent:
  
Com que els subproblemes es tornen a avaluar, aquest problema té la propietat de subproblemes superposats. Per tant, el problema de la motxilla 0/1 té les dues propietats (vegeu això i això ) d'un problema de programació dinàmica. Com altres típics Problemes de programació dinàmica (DP). , el recàlcul dels mateixos subproblemes es pot evitar construint una matriu temporal K[][] de manera ascendente.
 
    Il·lustració:    
 
A continuació es mostra la il·lustració de l'enfocament anterior:
  
Deixar,    pes[] = {1, 2, 3}, benefici[] = {10, 15, 40}, capacitat = 6    
 
Si no s'omple cap element, el benefici possible és 0.
weight⇢  
item⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
 
 
 
 
 
 
 
2
 
 
 
 
 
 
 
3
 
 
 
 
 
 
 
    Per omplir el primer article de la bossa:    Si seguim el procediment esmentat anteriorment, la taula es veurà com la següent.
weight⇢  
item⇣/
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
 
 
 
 
 
 
 
    Per omplir el segon element:       
Quan jthWeight = 2, el benefici màxim possible és màxim (10, DP[1][2-2] + 15) = màxim (10, 15) = 15.  
Quan jthWeight = 3, el benefici màxim possible és màxim (2 no es posa, 2 es posa a la bossa) = max (DP[1][3], 15+DP[1][3-2]) = màx (10, 25) = 25.
weight⇢  
item⇣/
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
15
25
25
25
25
3
 
 
 
 
 
 
 
    Per omplir el tercer element:     
Quan jthWeight = 3, el benefici màxim possible és max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.  
Quan jthWeight = 4, el benefici màxim possible és max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.  
Quan jthWeight = 5, el benefici màxim possible és max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.  
Quan jthWeight = 6, el benefici màxim possible és max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
weight⇢  
item⇣/
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
15
25
25
25
25
3
0
10
15
40
50
55
65
A continuació es mostra la implementació de l'enfocament anterior:
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; } // Retorna el valor màxim que // es pot posar en una motxilla de capacitat W int knapSack(int W, int wt[], int val[], int n) { int i, w;  vector> K(n + 1, vector (W + 1));  // Construeix la taula K[][] de baix a dalt per a (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; } // Retorna el valor màxim que // es pot posar en una motxilla de capacitat W int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[n + 1][W + 1];  // Construeix la taula K[][] de baix a dalt per a (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; } // Retorna el valor màxim que // es pot posar en una motxilla de capacitat W static int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[][] = nou int[n + 1][W + 1];  // Construeix la taula K[][] de baix a dalt per a (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; } // Retorna el valor màxim que // es pot posar en una motxilla de // capacitat W static int knapSack(int W, int[] wt, int[] val, int n) { int i, w;  int[, ] K = nou int[n + 1, W + 1];  // Construeix la taula K[][] a la part inferior // amunt per a (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;  } // Retorna el valor màxim que es pot // posar en una motxilla de capacitat W function knapSack(W, wt, val, n) { let i, w;  sigui K = nou Array (n + 1);    // Construeix la taula K[][] de baix a dalt per a (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. ?>>
   
  Sortida      Complexitat temporal:    O (N * W). on 'N' és el nombre d'elements i 'W' és la capacitat.  
    Espai auxiliar:    O (N * W). L'ús d'una matriu 2-D de mida 'N*W'.
 
    Enfocament optimitzat per l'espai per al problema de la motxilla 0/1 mitjançant la programació dinàmica:    
Per resoldre el problema seguiu la idea següent:
  
Per calcular la fila actual de la matriu dp[] només necessitem la fila anterior, però si comencem a recórrer les files de dreta a esquerra, només es pot fer amb una sola fila.
convertir cadena en enter
 
A continuació es mostra la implementació de l'enfocament anterior:
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--) { si (pes [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--) { si (pes [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--) { si (pes [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--) { si (pes [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>
   
  Sortida  
220>
 
    Complexitat temporal    : O (N * W). Com s'eviten els càlculs redundants d'estats  
    Espai Auxiliar    : O(W) Com que estem utilitzant una matriu 1-D en lloc d'una matriu 2-D