Forutsetninger: Introduksjon til ryggsekkproblemet, dets typer og hvordan de løses

Gitt N varer hvor hver vare har en viss vekt og fortjeneste knyttet til seg og også gitt en pose med kapasitet I , [dvs. posen kan holde på det meste I vekt i den]. Oppgaven er å legge varene i posen slik at summen av fortjeneste knyttet til dem er maksimalt mulig.

Merk: Begrensningen her er at vi enten kan legge en vare helt inn i posen eller ikke kan legge den i det hele tatt [Det er ikke mulig å legge en del av en vare i posen].

Eksempler:

Inndata: N = 3, W = 4, fortjeneste[] = {1, 2, 3}, vekt[] = {4, 5, 1}
Produksjon: 3
Forklaring: Det er to varer som har vekt mindre enn eller lik 4. Hvis vi velger varen med vekt 4, er den mulige fortjenesten 1. Og hvis vi velger gjenstanden med vekt 1, er den mulige fortjenesten 3. Så maksimalt mulig fortjeneste er 3. Merk at vi ikke kan sette begge varene med vekt 4 og 1 sammen da kapasiteten til posen er 4.

Inndata: N = 3, W = 3, fortjeneste[] = {1, 2, 3}, vekt[] = {4, 5, 6}
Produksjon: 0

Rekursjonstilnærming for 0/1 nappsekkproblem:

Følg ideen nedenfor for å løse problemet:

En enkel løsning er å vurdere alle delmengder av varer og beregne totalvekten og fortjenesten til alle delmengdene. Vurder de eneste undergruppene hvis totale vekt er mindre enn W. Fra alle slike undermengder velger du undergruppen med maksimal fortjeneste.

les csv-filen i java

Optimal understruktur : For å vurdere alle undersett av elementer, kan det være to tilfeller for hvert element.

• Tilfelle 1: Elementet er inkludert i det optimale undersettet.
• Tilfelle 2: Varen er ikke inkludert i det optimale settet.

Følg trinnene nedenfor for å løse problemet:

Maksimumsverdien oppnådd fra 'N' elementer er maks av de følgende to verdiene.

• Tilfelle 1 (inkluder N^thvare): Verdien av N^thelement pluss maksimal verdi oppnådd ved gjenværende N-1 elementer og gjenværende vekt, dvs. (W-vekt av N^thpunkt).
• Tilfelle 2 (ekskluder N^thvare): Maksimal verdi oppnådd av N-1 varer og W vekt.
• Hvis vekten av 'N^th' element er større enn 'W', så kan ikke det N-te elementet inkluderes og Tilfelle 2 er den eneste muligheten.

Nedenfor er implementeringen av tilnærmingen ovenfor:

/* 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; } // Returnerer den maksimale verdien som // kan settes i en ryggsekk med kapasitet W int knapSack(int W, int wt[], int val[], int n) // Base Case if (n == 0 // Driverkode int main() { int fortjeneste[] = { 60, 100, 120 }; int W = 50 / int. 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; } // Returnerer den maksimale verdien som kan // legges i en ryggsekk med kapasitet W int knapSack(int W, int wt[], int val[], int n) W == 0) return 0;  // Hvis vekten av den n-te varen er mer enn // Ryggsekkkapasitet W, kan ikke denne gjenstanden // inkluderes i den optimale løsningen hvis (wt[n - 1]> W) returner ryggsekk(W, wt, val, n - 1);  // Returner maksimalt to tilfeller: // (1) n'te vare inkludert // (2) ikke inkludert else return max( val[n - 1] + ryggsekk(W - wt[n - 1], wt, val, n - 1), ryggsekk(W, wt, val, n - 1));  // Driverkode int main() { int profit[] = { 60, 100, 120 };  int vekt[] = { 10, 20, 30 };  int W = 50;  int n = sizeof(profit) / sizeof(profit[0]);  printf('%d', ryggsekk(W, vekt, fortjeneste, n));  returner 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) ? a:b; } // Returnerer den maksimale verdien som // kan legges i en ryggsekk med // kapasitet W static int knapSack(int W, int wt[], int val[], int n) // Driver code public static void main( String args[]) { int profit[] = new int[] { 60, 100, 120 };  int vekt[] = ny int[] { 10, 20, 30 };  int W = 50;  int n = profit.length;  System.out.println(knapSack(W, vekt, profitt, n));  } } /*Denne koden er bidratt av 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): returner ryggsekk(W, wt, val, n-1) # returner maksimalt to tilfeller: # (1) nte vare inkludert # (2) ikke inkludert annet: retur maks( val[n-1] + ryggsekk ( W-wt[n-1], wt, val, n-1), ryggsekk(W, wt, val, n-1)) # end of function ryggsekk # Driverkode hvis __navn__ == '__main__': profit = [60, 100, 120] weight = [10, 20, 30] W = 50 n = len(profit) print ryggsekk(W, weight, profit, n) # Denne koden er bidratt av 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) ? a:b; } // Returnerer den maksimale verdien som kan // settes i en ryggsekk med kapasitet W static int knapSack(int W, int[] wt, int[] val, int n) W == 0) return 0;  // Hvis vekten av den n-te varen er // mer enn Ryggsekkkapasitet W, // kan ikke denne gjenstanden // inkluderes i den optimale løsningen hvis (wt[n - 1]> W) returner ryggsekk(W, wt, val n-1);  // Returner maksimalt to tilfeller: // (1) n'te vare inkludert // (2) ikke inkludert else return max(val[n - 1] + ryggsekk(W - wt[n - 1], wt, val, n - 1), ryggsekk(W, wt, val, n - 1));    // Driverkode offentlig statisk void Main() { int[] profit = new int[] { 60, 100, 120 };  int[] vekt = ny int[] { 10, 20, 30 };  int W = 50;  int n = profitt.Length;  Console.WriteLine(knapSack(W, weight, profit, n));  } } // Denne koden er bidratt av 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) ? a:b;  } // Returnerer den maksimale verdien som kan // settes i en ryggsekk med kapasitet W funksjon ryggsekk(W, wt, val, n) // Base Case if (n == 0 la profitt = [ 60, 100, 120 ] ; la vekt = [ 10, 20, 30 ]; la n = profit.length;PHP>

220>

Tidskompleksitet: O(2^N)
Hjelpeplass: O(N), Stabelplass kreves for rekursjon

Dynamisk programmering tilnærming for 0/1 nappsekk-problem

Memoiseringstilnærming for 0/1 knepsekkproblem:

Merk: Det skal bemerkes at funksjonen ovenfor ved bruk av rekursjon beregner de samme delproblemene igjen og igjen. Se følgende rekursjonstre, K(1, 1) blir evaluert to ganger.

I følgende rekursjonstre, K() refererer til ryggsekk(). De to parameterne som er angitt i følgende rekursjonstre er n og W.
Rekursjonstreet er for følgende eksempelinndata.
vekt[] = {1, 1, 1}, B = 2, fortjeneste[] = {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)

Rekursjonstre for ryggsekk kapasitet 2 enheter og 3 gjenstander med 1 vektenhet.

Ettersom det er gjentakelser av samme delproblem igjen og igjen, kan vi implementere følgende idé for å løse problemet.

Hvis vi får et delproblem første gang, kan vi løse dette problemet ved å lage en 2D-matrise som kan lagre en bestemt tilstand (n, w). Nå hvis vi kommer over den samme tilstanden (n, w) igjen i stedet for å beregne den i eksponentiell kompleksitet, kan vi direkte returnere resultatet lagret i tabellen i konstant tid.

10 av 60

Nedenfor er implementeringen av tilnærmingen ovenfor:

// 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) { // Lagre verdien av funksjonskall // stack i tabell før retur dp[indeks][W] = knapSackRec(W, wt, val, index - 1, dp);  return dp[indeks][W];  } else { // Lagre verdi i en tabell før retur dp[indeks][W] = max(val[indeks] + knapSackRec(W - wt[indeks], wt, val, index - 1, dp), knapSackRec(W) , vekt, val, indeks - 1, dp));  // Returverdi av tabell etter lagring av retur dp[indeks][W];  } } int knapSack(int W, int wt[], int val[], int n) { // dobbelpeker for å erklære //-tabellen dynamisk int** dp;  dp = ny int*[n];  // loop for å lage tabellen dynamisk 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) ? a:b; } // Returnerer verdien av maksimal fortjeneste statisk int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) W == 0) return 0;  if (dp[n][W] != -1) returner dp[n][W];  if (wt[n - 1]> W) // Lagre verdien av funksjonskall // stack i tabell før retur return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);  else // Returner verdi av tabellen etter lagring av retur dp[n][W] = max((val[n - 1] + ryggSakkRec(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) { // Deklarer tabellen dynamisk int dp[][] = new int[N + 1][W + 1];  // Loop for å opprinnelig fylt //-tabellen med -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] = ryggsekk(wt, val, W, n-1) return t[n][W] # Førerkode hvis __navn__ == '__main__': profit = [60, 100, 120] vekt = [10, 20, 30] W = 50 n = len(profit) # Vi initialiserer matrisen med -1 først. t = [[-1 for i in range(W + 1)] for j in range(n + 1)] print(knapspack(weight, profit, W, n)) # Denne koden er bidratt av Prosun Kumar Sarkar>'>C# 
// A utility function that returns // maximum of two integers  function max(a, b)  {   return (a>b) ? a:b;  } // Returnerer verdien av maksimal profittfunksjon knapSackRec(W, wt, val, n,dp) // Base condition if (n == 0 function knapSack( W, wt,val,N) { // Deklarer dp-tabellen dynamisk // Intialiserer dp-tabeller(rad og kolonner) med -1 under 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 = [ 60, 100, 120 ]; ; console.log(knapSack(W, vekt, profit, N));  
  Produksjon  
220>
  
    Tidskompleksitet:    O(N * W). Ettersom overflødige beregninger av stater unngås.  
    Hjelpeplass:    O(N * W) + O(N). Bruken av en 2D-array-datastruktur for lagring av mellomtilstander og O(N) ekstra stabelplass (ASS) har blitt brukt for rekursjonsstabel
 
    Bottom-up-tilnærming for 0/1 nappsekkproblem:    
Følg ideen nedenfor for å løse problemet:
  
Siden underproblemer evalueres på nytt, har dette problemet Overlapping Sub-problems-egenskapen. Så 0/1 Knapsack-problemet har begge egenskapene (se dette og dette ) av et dynamisk programmeringsproblem. Som andre typiske Dynamisk programmering (DP) problemer , kan re-beregning av de samme underproblemene unngås ved å konstruere en midlertidig array K[][] på en nedenfra og opp-måte.
 
    Illustrasjon:    
 
Nedenfor er illustrasjonen av tilnærmingen ovenfor:
  
La,    vekt[] = {1, 2, 3}, fortjeneste[] = {10, 15, 40}, kapasitet = 6    
 
Hvis ingen element er fylt ut, er den mulige fortjenesten 0.
vekt⇢  
vare⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
 
 
 
 
 
 
 
2
 
 
 
 
 
 
 
3
 
 
 
 
 
 
 
    For å fylle den første gjenstanden i posen:    Hvis vi følger prosedyren ovenfor, vil tabellen se slik ut.
vekt⇢  
vare⇣/
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
 
 
 
 
 
 
 
    For å fylle det andre elementet:       
Når jthWeight = 2, er maksimalt mulig fortjeneste maks (10, DP[1][2-2] + 15) = max(10, 15) = 15.  
Når jthWeight = 3, så er maksimal mulig fortjeneste maks(2 ikke satt, 2 legges i posen) = max(DP[1][3], 15+DP[1][3-2]) = max(10, 25) = 25.
vekt⇢  
vare⇣/
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
femten
25
25
25
25
3
 
 
 
 
 
 
 
    For å fylle ut det tredje elementet:     
Når jthWeight = 3, er maksimalt mulig fortjeneste max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.  
Når jthWeight = 4, er maksimalt mulig fortjeneste max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.  
Når jthWeight = 5, er maksimalt mulig fortjeneste max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.  
Når jthWeight = 6, er maksimalt mulig fortjeneste max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
vekt⇢  
vare⇣/
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
femten
25
25
25
25
3
0
10
femten
40
femti
55
65
Nedenfor er implementeringen av tilnærmingen ovenfor:
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; } // Returnerer den maksimale verdien som // kan legges i en ryggsekk med kapasitet W int knapSack(int W, int wt[], int val[], int n) { int i, w;  vektor> K(n + 1, vektor (W + 1));  // Bygg tabell K[][] nedenfra og opp for (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; } // Returnerer den maksimale verdien som // kan legges i en ryggsekk med kapasitet W int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[n + 1][W + 1];  // Bygg tabell K[][] nedenfra og opp for (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; } // Returnerer den maksimale verdien som kan // settes i en ryggsekk med kapasitet W static int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[][] = ny int[n + 1][W + 1];  // Bygg tabell K[][] nedenfra og opp for (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; } // Returnerer den maksimale verdien som // kan legges i en ryggsekk med // kapasitet W static int knapSack(int W, int[] wt, int[] val, int n) { int i, w;  int[, ] K = ny int[n + 1, W + 1];  // Bygg tabell K[][] i bunnen // opp måte for (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;  } // Returnerer den maksimale verdien som kan // legges i en ryggsekk med kapasitet W-funksjon ryggsekk(W, wt, val, n) { la i, w;  la K = ny Array(n + 1);    // Bygg tabell K[][] nedenfra og opp for (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. ?>>
   
  Produksjon      Tidskompleksitet:    O(N * W). der 'N' er antall elementer og 'W' er kapasitet.  
    Hjelpeplass:    O(N * W). Bruken av en 2D-array i størrelsen 'N*W'.
Java eksempel programmer
 
    Plassoptimalisert tilnærming for 0/1 napsekkproblem ved bruk av dynamisk programmering:    
Følg ideen nedenfor for å løse problemet:
  
For å beregne gjeldende rad i dp[]-matrisen trenger vi bare forrige rad, men hvis vi begynner å krysse radene fra høyre til venstre, kan det gjøres med kun en enkelt rad
 
Nedenfor er implementeringen av tilnærmingen ovenfor:
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>
   
  Produksjon  
220>
 
    Tidskompleksitet    : O(N * W). Ettersom overflødige beregninger av stater unngås  
    Auxiliary Space    : O(W) Siden vi bruker en 1-D-matrise i stedet for en 2-D-matrise