/* 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; } // Atgriež maksimālo vērtību, ko // var ievietot mugursomā ar ietilpību W int knapSack(int W, int wt[], int val[], int n) // Pamata gadījums, ja (n == 0 // Vadītāja kods int main() { int peļņa[] = { 60, 100, 120 } = { 10, 20, 30 } int W = 50 int n = lielums(peļņa) 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; } // Atgriež maksimālo vērtību, ko // var ievietot mugursomā ar ietilpību W int knapSack(int W, int wt[], int val[], int n) W == 0) return 0;  // Ja n-tās preces svars ir lielāks par // Mugursomas ietilpība W, tad šo preci // nevar iekļaut optimālajā risinājumā, ja (wt[n - 1]> W) return knapSack(W, wt, val, n - 1);  // Atgriezt ne vairāk kā divus gadījumus: // (1) nth vienums iekļauts // (2) nav iekļauts cits return max( val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));  // Draivera kods int main() { int peļņa[] = { 60, 100, 120 };  iekšējais svars[] = {10, 20, 30};  int W = 50;  int n = lielums(peļņa) / lielums(peļņa[0]);  printf('%d', knapSack(W, svars, peļņa, n));  atgriezties 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; } // Atgriež maksimālo vērtību, ko // var ievietot mugursomā ar // ietilpību W static int knapSack(int W, int wt[], int val[], int n) // Draivera kods public static void main( Virkne args[]) { int peļņa[] = jauns int[] { 60, 100, 120 };  int svars[] = jauns int[] { 10, 20, 30 };  int W = 50;  int n = peļņa.garums;  System.out.println(knapSack(W, svars, peļņa, n));  } } /*Šo kodu ir sagatavojis 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): atgriezt knapSack(W, wt, val, n-1) # atgriezt ne vairāk kā divus gadījumus: # (1) n-tā prece iekļauta # (2) nav iekļauta cita: return max( val[n-1] + knapSack ( W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # funkcijas beigas knapSack # Draivera kods, ja __name__ == '__main__': peļņa = [60, 100, 120] svars = [10, 20, 30] W = 50 n = lēca(peļņa) drukāt mugursoma(W, svars, peļņa, n) # Šo kodu ir sagatavojis Nikhils Kumars Singhs>>C#b)? a : b;  } // Atgriež maksimālo vērtību, ko // var ievietot mugursomā ar ietilpību W knapSack(W, wt, val, n) // Pamata gadījums if (n == 0 let profit = [ 60, 100, 120 ] ļaujiet svaram = [ 10, 20, 30 ], lai n = peļņa. konsole.log(W, svars, n);PHP220>

// 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) { // Saglabājiet funkcijas izsaukuma vērtību // steka vērtību tabulā pirms atgriešanās dp[indekss][W] = knapSackRec(W, wt, val, index - 1, dp);  atgriezties dp[indekss][W];  } else { // Saglabāt vērtību tabulā pirms atgriešanās dp[indekss][W] = max(val[index] + knapSackRec(W - wt[index], wt, val, index - 1, dp), knapSackRec(W , wt, val, indekss - 1, dp));  // Tabulas atgriešanas vērtība pēc atgriešanās dp[indekss][W] saglabāšanas;  } } int knapSack(int W, int wt[], int val[], int n) { // dubultā rādītājs, lai dinamiski deklarētu // tabulu int** dp;  dp = jauns int*[n];  // cilpa, lai dinamiski izveidotu tabulu (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; } // Atgriež maksimālās peļņas vērtību static int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) W == 0) return 0;  if (dp[n][W] != -1) atgriež dp[n][W];  if (wt[n - 1]> W) // Saglabājiet funkcijas izsaukuma // steka vērtību tabulā pirms atgriešanās return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);  else // Tabulas atgriešanas vērtība pēc atgriešanās 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) { // Dinamiski deklarēt tabulu int dp[][] = new int[N + 1][W + 1];  // Cilpa, lai sākotnēji aizpildītu // tabulu ar -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] = mugursoma (wt, val, W, n-1) atgriež t[n][W] # Draiveris kods, ja __name__ == '__main__': peļņa = [60, 100, 120] svars = [10, 20, 30] W = 50 n = len(peļņa) # Sākumā matricu inicializējam ar -1. t = [[-1 i diapazonā(W + 1)] j diapazonā(n + 1)] print(mugursoma(svars, peļņa, W, n)) # Šo kodu ir sagatavojis Prosuns Kumars Sarkars>'>C# 
// A utility function that returns // maximum of two integers  function max(a, b)  {   return (a>b)? a : b;  } // Atgriež maksimālās peļņas funkcijas knapSackRec(W, wt, val, n,dp) vērtību // Pamatnosacījums if (n == 0 function knapSack( W, wt,val,N) { // Deklarēt dp tabulu dinamiski // Indijalizing dp tabulas(rinda un kolonnas) ar -1 zem 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)) // Šo kodu sniedza akshitsaxenaa09  
  Izvade      Laika sarežģītība:    O(Z*W). Tā kā tiek novērsti lieki stāvokļu aprēķini.  
    Palīgtelpa:    O(N*W)+O(N). 2D masīva datu struktūras izmantošana starpstāvokļu un O(N) papildu steka telpas (ASS) glabāšanai ir izmantota rekursijas stekam.
 
    Augšupēja pieeja 0/1 mugursomas problēmai:    
Lai atrisinātu problēmu, izpildiet šādu ideju:
  
Tā kā apakšproblēmas tiek novērtētas vēlreiz, šai problēmai ir pārklāšanās apakšproblēmu īpašums. Tātad 0/1 mugursomas problēmai ir abas īpašības (sk šis un šis ) dinamiskas programmēšanas problēma. Tāpat kā citi tipiski Dinamiskās programmēšanas (DP) problēmas , var izvairīties no to pašu apakšproblēmu atkārtotas aprēķināšanas, izveidojot pagaidu masīvu K[][] augšupvērsti.
 
    Ilustrācija:    
 
Tālāk ir parādīta iepriekš minētās pieejas ilustrācija:
java virknes formāts
  
Ļaujiet,    svars[] = {1, 2, 3}, peļņa[] = {10, 15, 40}, ietilpība = 6    
 
Ja neviens elements nav aizpildīts, tad iespējamā peļņa ir 0.
svars⇢  
prece⇣/
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
 
 
 
 
 
 
 
2
 
 
 
 
 
 
 
3
 
 
 
 
 
 
 
    Pirmās preces iepildīšanai maisā:    Ja sekosim iepriekšminētajai procedūrai, tabula izskatīsies šādi.
svars⇢  
prece⇣/
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
 
 
 
 
 
 
 
    Otrās vienības aizpildīšanai:       
Ja jthWeight = 2, tad maksimālā iespējamā peļņa ir max (10, DP[1][2-2] + 15) = max(10, 15) = 15.  
Ja jthWeight = 3, tad maksimālā iespējamā peļņa ir max(2 nav ievietoti, 2 tiek ievietoti maisā) = max(DP[1][3], 15+DP[1][3-2]) = max(10, 25) = 25.
svars⇢  
prece⇣/
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
piecpadsmit
25
25
25
25
3
 
 
 
 
 
 
 
    Trešās pozīcijas aizpildīšanai:     
Ja jthWeight = 3, maksimālā iespējamā peļņa ir max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.  
Ja jthWeight = 4, maksimālā iespējamā peļņa ir max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.  
Ja jthWeight = 5, maksimālā iespējamā peļņa ir max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.  
Ja jthWeight = 6, maksimālā iespējamā peļņa ir max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
svars⇢  
prece⇣/
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
piecpadsmit
25
25
25
25
3
0
10
piecpadsmit
40
piecdesmit
55
65
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.
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; } // Atgriež maksimālo vērtību, ko // var ievietot mugursomā ar ietilpību W int knapSack(int W, int wt[], int val[], int n) { int i, w;  vektors> K(n + 1, vektors (W + 1));  // Veidot tabulu K[][] no apakšas uz augšu priekš (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; } // Atgriež maksimālo vērtību, ko // var ievietot mugursomā ar ietilpību W int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[n + 1][W + 1];  // Veidot tabulu K[][] no apakšas uz augšu priekš (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; } // Atgriež maksimālo vērtību, ko // var ievietot mugursomā ar ietilpību W static int knapSack(int W, int wt[], int val[], int n) { int i, w;  int K[][] = jauns int[n + 1][W + 1];  // Veidot tabulu K[][] no apakšas uz augšu priekš (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; } // Atgriež maksimālo vērtību, ko // var ievietot mugursomā ar // ietilpību W static int knapSack(int W, int[] wt, int[] val, int n) { int i, w;  int[, ] K = jauns int[n + 1, W + 1];  // Veidot tabulu K[][] apakšā // uz augšu priekš (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;  } // Atgriež maksimālo vērtību, ko // var ievietot mugursomā ar kapacitāti W funkcija knapSack(W, wt, val, n) { let i, w;  lai K = jauns Masīvs(n + 1);    // Veidot tabulu K[][] no apakšas uz augšu priekš (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. ?>>>  
  Izvade      Laika sarežģītība:    O(Z*W). kur “N” ir elementu skaits un “W” ir ietilpība.  
    Palīgtelpa:    O(Z*W). Divdimensiju masīva izmantošana ar izmēru “N*W”.
 
    Vietai optimizēta pieeja 0/1 mugursomas problēmai, izmantojot dinamisko programmēšanu:    
Lai atrisinātu problēmu, izpildiet šādu ideju:
  
Lai aprēķinātu pašreizējo dp[] masīva rindu, ir nepieciešama tikai iepriekšējā rinda, bet, ja mēs sākam šķērsot rindas no labās uz kreiso, tad to var izdarīt tikai ar vienu rindu
 
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.
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>
   
  Izvade      Laika sarežģītība    : O(Z*W). Tā kā tiek novērsti lieki stāvokļu aprēķini  
    Palīgtelpa    : O(W) Tā kā mēs izmantojam 1-D masīvu, nevis 2-D masīvu