/* 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) ? un:b; } // Restituisce il valore massimo che // può essere messo in uno zaino di capacità W int knapSack(int W, int wt[], int val[], int n) // Base Case if (n == 0 // Codice driver int main() { int profitto[] = { 60, 100, 120 }; int peso[] = { 10, 20, 30 }; int W = 50; int n = sizeof(profitto[ 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) ? un:b; } // Restituisce il valore massimo che può // essere messo in uno zaino di capacità W int knapSack(int W, int wt[], int val[], int n) W == 0) return 0;  // Se il peso dell'n-esimo oggetto è maggiore // della capacità dello zaino W, allora questo oggetto non può // essere incluso nella soluzione ottima if (wt[n - 1]> W) return knapSack(W, wt, val, n -1);  // Restituisce il massimo di due casi: // (1) n-esimo elemento incluso // (2) non incluso altrimenti restituisce max( val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), zaino(W, wt, val, n - 1));  // Codice driver int main() { int profit[] = { 60, 100, 120 };  int peso[] = { 10, 20, 30 };  intero W = 50;  int n = sizeof(profitto) / sizeof(profitto[0]);  printf('%d', zaino(W, peso, profitto, n));  restituire 0; }>

/* 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) ? un:b; } // Restituisce il valore massimo che // può essere messo in uno zaino di // capacità W static int knapSack(int W, int wt[], int val[], int n) // Codice driver public static void main( String argomenti[]) { int profitto[] = new int[] { 60, 100, 120 };  int peso[] = nuovo int[] { 10, 20, 30 };  intero W = 50;  int n = profitto.lunghezza;  System.out.println(zaino(W, peso, profitto, n));  } } /*Questo codice è un contributo di Rajat Mishra */>

# 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 zaino(W, wt, val, n-1) # restituisce il massimo di due casi: # (1) n-esimo oggetto incluso # (2) non incluso altrimenti: return max( val[n-1] + zaino ( W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # fine della funzione knapSack # Codice driver if __name__ == '__main__': profitto = [60, 100, 120] peso = [10, 20, 30] W = 50 n = len(profitto) print zaino(W, peso, profitto, n) # Questo codice è un contributo di Nikhil Kumar Singh>

/* 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) ? un:b; } // Restituisce il valore massimo che // può essere messo in uno zaino di capacità W static int knapSack(int W, int[] wt, int[] val, int n) W == 0) return 0;  // Se il peso dell'n-esimo oggetto è // superiore alla capacità dello zaino W, // allora questo oggetto non può essere // incluso nella soluzione ottima if (wt[n - 1]> W) return knapSack(W, wt, val , n-1);  // Restituisce il massimo di due casi: // (1) ennesimo elemento incluso // (2) non incluso altrimenti restituisce max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), zaino(W, wt, val, n - 1));    // Codice driver public static void Main() { int[] profit = new int[] { 60, 100, 120 };  int[] peso = nuovo int[] { 10, 20, 30 };  int W = 50;  int n = profitto.Lunghezza;  Console.WriteLine(knapSack(W, peso, profitto, n));  } } // Questo codice è fornito da Sam007>

 /* 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) ? un:b;  } // Restituisce il valore massimo che può // essere messo in uno zaino di capacità W funzione knapSack(W, wt, val, n) // Caso base if (n == 0 let profit = [ 60, 100, 120 ] ; lascia peso = [ 10, 20, 30 ]; lascia W = 50; lascia n = profitto.lunghezza;console.log(knapSack(W, peso, profitto, n));PHP220>

Complessità temporale: O(2^N)
Spazio ausiliario: O(N), spazio nello stack richiesto per la ricorsione

Approccio di programmazione dinamica per il problema dello zaino 0/1

Approccio alla memorizzazione per il problema dello zaino 0/1:

Nota: Va notato che la funzione di cui sopra che utilizza la ricorsione calcola gli stessi sottoproblemi ancora e ancora. Vedere il seguente albero di ricorsione, K(1, 1) viene valutato due volte.

Nel seguente albero di ricorsione, K() si riferisce a zaino(). I due parametri indicati nel seguente albero di ricorsione sono n e W.
L'albero di ricorsione serve per i seguenti input di esempio.
peso[] = {1, 1, 1}, W = 2, profitto[] = {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)

Albero di ricorsione per capacità zaino 2 unità e 3 articoli di 1 unità di peso.

Poiché ci sono ripetizioni dello stesso sottoproblema ancora e ancora, possiamo implementare la seguente idea per risolvere il problema.

Se otteniamo un sottoproblema la prima volta, possiamo risolverlo creando un array 2D in grado di memorizzare un particolare stato (n, w). Ora, se ci imbattiamo nuovamente nello stesso stato (n, w), invece di calcolarlo in complessità esponenziale, possiamo restituire direttamente il suo risultato memorizzato nella tabella in tempo costante.

rimuove l'ultimo carattere dalla stringa

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

// 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) { // Memorizza il valore della chiamata di funzione // stack nella tabella prima di restituire dp[index][W] = knapSackRec(W, wt, val, indice - 1, dp);  return dp[indice][W];  } else { // Memorizza il valore in una tabella prima di restituire dp[indice][W] = max(val[indice] + knapSackRec(W - wt[indice], wt, val, indice - 1, dp), knapSackRec(W , peso, val, indice - 1, dp));  // Restituisce il valore della tabella dopo aver memorizzato return dp[index][W];  } } int knapSack(int W, int wt[], int val[], int n) { // doppio puntatore per dichiarare dinamicamente // la tabella int** dp;  dp = nuovo int*[n];  // ciclo per creare dinamicamente la tabella for (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) ? un:b; } // Restituisce il valore del profitto massimo 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) // Memorizza il valore della chiamata di funzione // stack nella tabella prima di return return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);  else // Restituisce il valore della tabella dopo aver memorizzato return dp[n][W] = max((val[n - 1] + knapSackRec(W - wt[n - 1], wt, val, n - 1, dp)) , knapSackRec(W, peso, val, n - 1, dp));    static int knapSack(int W, int wt[], int val[], int N) { // Dichiara la tabella dinamicamente int dp[][] = new int[N + 1][W + 1];  // Ripete il ciclo per riempire inizialmente // la tabella con -1 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] = zaino(wt, val, W, n-1) return t[n][W] # Codice conducente if __nome__ == '__main__': profitto = [60, 100, 120] peso = [10, 20, 30] W = 50 n = len(profitto) # Inizialmente inizializziamo la matrice con -1. t = [[-1 for i in range(W + 1)] for j in range(n + 1)] print(zaino(peso, profitto, W, n)) # Questo codice è fornito da Prosun Kumar Sarkar>'>C# 
// A utility function that returns // maximum of two integers  function max(a, b)  {   return (a>B) ? un:b;  } // Restituisce il valore del profitto massimo funzione knapSackRec(W, wt, val, n,dp) // Condizione di base if (n == 0 function knapSack( W, wt,val,N) { // Dichiara la tabella dp dinamicamente // Inizializzo le tabelle dp (riga e colonne) con -1 sotto var dp = new Array(N+1).fill(-1).map(el => new Array(W+1).fill(-1) ); return knapSackRec(W, wt, val, N, dp); var profitto= [ 60, 100, 120 ]; var peso = [ 10, 20, 30 ]; ; console.log(knapSack(W, peso, profitto, N)); // Questo codice è fornito da akshitsaxenaa09>
   
  Produzione  
220>
 
    Complessità temporale:    O(N*W). Poiché si evitano calcoli ridondanti degli stati.  
    Spazio ausiliario:    O(N * W) + O(N). Per lo stack di ricorsione è stato utilizzato l'uso di una struttura dati array 2D per la memorizzazione degli stati intermedi e dello spazio stack ausiliario O(N) (ASS)
 
    Approccio dal basso verso l'alto per il problema dello zaino 0/1:    
Per risolvere il problema seguire l'idea seguente:
film
  
Poiché i sottoproblemi vengono valutati nuovamente, questo problema ha la proprietà Sottoproblemi sovrapposti. Quindi il problema dello Zaino 0/1 ha entrambe le proprietà (vedi Questo E Questo ) di un problema di programmazione dinamica. Come altri tipici Problemi di Programmazione Dinamica (DP). , il ricalcolo degli stessi sottoproblemi può essere evitato costruendo un array temporaneo K[][] in modo bottom-up.
 
    Illustrazione:    
 
Di seguito è riportato l'illustrazione dell'approccio di cui sopra:
  
Permettere,    peso[] = {1, 2, 3}, profitto[] = {10, 15, 40}, Capacità = 6    
 
Se nessun elemento viene riempito, il profitto possibile è 0.
peso⇢  
oggetto⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
 
 
 
 
 
 
 
2
 
 
 
 
 
 
 
3
 
 
 
 
 
 
 
    Per riempire il primo oggetto nel sacchetto:    Se seguiamo la procedura sopra menzionata, la tabella sarà simile alla seguente.
peso⇢  
oggetto⇣/
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 compilare il secondo elemento:       
Quando jthWeight = 2, il profitto massimo possibile è max (10, DP[1][2-2] + 15) = max(10, 15) = 15.  
Quando jthWeight = 3, il massimo profitto possibile è max(2 non messi, 2 messi nel sacchetto) = max(DP[1][3], 15+DP[1][3-2]) = max(10, 25) = 25.
peso⇢  
oggetto⇣/
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
quindici
25
25
25
25
3
 
 
 
 
 
 
 
    Per compilare il terzo elemento:     
Quando jthWeight = 3, il profitto massimo possibile è max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.  
Quando jthWeight = 4, il profitto massimo possibile è max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.  
Quando jthWeight = 5, il profitto massimo possibile è max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.  
Quando jthWeight = 6, il massimo profitto possibile è max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
peso⇢  
oggetto⇣/
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
quindici
25
25
25
25
3
0
10
quindici
40
cinquanta
55
65
Di seguito è riportata l’implementazione dell’approccio di cui sopra:
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) ? un:b; } // Restituisce il valore massimo che // può essere messo in uno zaino di capacità W int knapSack(int W, int wt[], int val[], int n) { int i, w;  vettore> K(n + 1, vettore (W + 1));  // Costruisce la tabella K[][] in modalità bottom up per (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) ? un:b; } // Restituisce il valore massimo che // può essere messo in uno zaino di capacità W int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[n+1][W+1];  // Costruisce la tabella K[][] in modalità bottom up per (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; }>
 Giava 
// 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) ? un:b; } // Restituisce il valore massimo che // può essere messo in uno zaino di capacità W static int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[][] = nuovo int[n + 1][W + 1];  // Costruisce la tabella K[][] in modalità bottom up per (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 */>
 Pitone 
# 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) ? un:b; } // Restituisce il valore massimo che // può essere messo in uno zaino di // capacità W static int knapSack(int W, int[] wt, int[] val, int n) { int i, w;  int[, ] K = nuovo int[n + 1, W + 1];  // Costruisce la tabella K[][] in basso // verso l'alto per (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) ? un:b;  } // Restituisce il valore massimo che può // essere messo in uno zaino di capacità W function knapSack(W, wt, val, n) { let i, w;  lascia K = nuovo Array(n + 1);    // Costruisce la tabella K[][] in modalità bottom up per (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. ?>>
   
  Produzione  
220>
 
    Complessità temporale:    O(N*W). dove 'N' è il numero di elementi e 'W' è la capacità.  
    Spazio ausiliario:    O(N*W). L'uso di un array 2D di dimensione 'N*W'.
 
    Approccio ottimizzato in termini di spazio per il problema dello zaino 0/1 utilizzando la programmazione dinamica:    
Per risolvere il problema seguire l'idea seguente:
  
Per calcolare la riga corrente dell'array dp[] abbiamo bisogno solo della riga precedente, ma se iniziamo a percorrere le righe da destra a sinistra allora possiamo farlo solo con una singola riga
 
Di seguito è riportata l’implementazione dell’approccio di cui sopra:
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--) { se (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; }>
 Giava 
// 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--) { se (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>
 Pitone 
# 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--) { se (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--) { se (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>
   
  Produzione  
220>
 
    Complessità temporale    : O(N * W). Poiché si evitano calcoli ridondanti degli stati  
    Spazio ausiliario    : O(W) Poiché stiamo utilizzando un array 1-D invece di un array 2-D