Edellytykset: Johdatus reppuongelmaan, sen tyyppeihin ja niiden ratkaisemiseen
Annettu N kohteita, joissa jokaisella esineellä on jonkin verran painoa ja tuottoa, ja niille annetaan myös pussi, jossa on kapasiteetti SISÄÄN , [eli pussiin mahtuu korkeintaan SISÄÄN paino siinä]. Tehtävänä on laittaa tavarat pussiin niin, että niihin liittyvä voittosumma on mahdollisimman suuri.
Huomautus: Rajoite tässä on se, että voimme joko laittaa esineen kokonaan pussiin tai emme voi laittaa sitä ollenkaan [Ei ole mahdollista laittaa osaa esineestä pussiin].
Esimerkkejä:
Suositeltu käytäntö 0–1 Reppuongelma Kokeile!Syöte: N = 3, W = 4, voitto[] = {1, 2, 3}, paino[] = {4, 5, 1}
Lähtö: 3
Selitys: On olemassa kaksi tuotetta, joiden paino on pienempi tai yhtä suuri kuin 4. Jos valitsemme tuotteen painolla 4, mahdollinen voitto on 1. Ja jos valitsemme tuotteen painolla 1, mahdollinen voitto on 3. Eli suurin mahdollinen voitto on 3. Huomaa, että emme voi yhdistää sekä 4 että 1 painoisia tuotteita, koska pussin kapasiteetti on 4.Syöte: N = 3, W = 3, voitto[] = {1, 2, 3}, paino[] = {4, 5, 6}
Lähtö: 0
Rekursiomenetelmä 0/1-reppu-ongelmalle:
Ratkaise ongelma noudattamalla alla olevaa ideaa:
Yksinkertainen ratkaisu on ottaa huomioon kaikki kohteiden osajoukot ja laskea kaikkien osajoukkojen kokonaispaino ja voitto. Harkitse ainoita osajoukkoja, joiden kokonaispaino on pienempi kuin W. Valitse kaikista sellaisista osajoukoista se osajoukko, jolla on suurin hyöty.
täysi lomakeOptimaalinen alusrakenne : Kaikkien kohteiden osajoukkojen huomioon ottamiseksi jokaiselle kohteelle voi olla kaksi tapausta.
- Tapaus 1: Kohde sisältyy optimaaliseen osajoukkoon.
- Tapaus 2: Tuote ei sisälly optimaaliseen sarjaan.
Ratkaise ongelma noudattamalla alla olevia ohjeita:
'N' kohteista saatu enimmäisarvo on kahden seuraavan arvon enimmäisarvo.
- Tapaus 1 (mukaan lukien Ntherä): N:n arvothnimike plus enimmäisarvo, joka saadaan jäljellä olevasta N-1 tuotteesta ja jäljellä olevasta painosta, eli (N:n W-painotherä).
- Tapaus 2 (ei sisällä Nthitem): Suurin arvo, joka saadaan N-1 tuotteella ja W-painolla.
- Jos 'Nth' kohde on suurempi kuin 'W', niin N:ttä kohdetta ei voida sisällyttää ja Tapaus 2 on ainoa mahdollisuus.
Alla on yllä olevan lähestymistavan toteutus:
C++ /* 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; } // Palauttaa maksimiarvon, joka // voidaan laittaa reppuun, jonka kapasiteetti on W int knapSack(int W, int wt[], int val[], int n) // Perustapaus, jos (n == 0 // Ohjainkoodi int main() { int voitto[] = { 60, 100, 120 } = { 10, 20, 30 } int W = 50 int n = koko(voitto) 0]);<< knapSack(W, weight, profit, n); return 0; } // This code is contributed by rathbhupendra> C /* 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; } // Palauttaa maksimiarvon, joka voidaan // laittaa reppuun, jonka kapasiteetti on W int knapSack(int W, int wt[], int val[], int n) W == 0) return 0; // Jos n:nnen tuotteen paino on suurempi kuin // Repun kapasiteetti W, tätä tuotetta ei // voida sisällyttää optimaaliseen ratkaisuun, jos (wt[n - 1]> W) return reppureppu(W, wt, val, n -1); // Palauta enintään kaksi tapausta: // (1) n. nimike sisältyy // (2) ei sisälly muuten return max( val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1)); // Ohjainkoodi int main() { int voitto[] = { 60, 100, 120 }; int paino[] = { 10, 20, 30 }; int W = 50; int n = koko(voitto) / koko(voitto[0]); printf('%d', knapSack(W, paino, voitto, n)); paluu 0; }> Java /* 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; } // Palauttaa maksimiarvon, joka // voidaan laittaa reppuun // kapasiteetin W static int knapSack(int W, int wt[], int val[], int n) // Ohjainkoodi public static void main( Merkkijono args[]) { int voitto[] = uusi int[] { 60, 100, 120 }; int paino[] = uusi int[] { 10, 20, 30 }; int W = 50; int n = voitto.pituus; System.out.println(knapPack(W, paino, voitto, n)); } } /*Tämän koodin on toimittanut Rajat Mishra */> Python # 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 knapPack(W, wt, val, n-1) # palauta enintään kaksi tapausta: # (1) n:s tuote mukana # (2) ei sisälly muu: return max( val[n-1] + knapPack ( W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # funktion loppu knapSack # Ohjainkoodi, jos __name__ == '__main__': voitto = [60, 100, 120] paino = [10, 20, 30] L = 50 n = len(voitto) tulosta knapack(W, paino, voitto, n) # Tämän koodin on antanut 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; } // Palauttaa maksimiarvon, joka // voidaan laittaa reppuun, jonka kapasiteetti on W staattinen int reppu (int W, int[] wt, int[] val, int n) W == 0) return 0; // Jos n:nnen tuotteen paino on // suurempi kuin repun kapasiteetti W, // tätä tuotetta ei // voida sisällyttää optimaaliseen ratkaisuun, jos (wt[n - 1]> W) return reppureppu(W, wt, val n - 1); // Palauta enintään kaksi tapausta: // (1) n. tuote sisältyy // (2) ei sisälly muuten return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1)); // Ohjainkoodi public static void Main() { int[] voitto = uusi int[] { 60, 100, 120 }; int[] paino = uusi int[] { 10, 20, 30 }; int W = 50; int n = voitto.Pituus; Console.WriteLine(knapPack(W, paino, voitto, n)); } } // Tämän koodin on toimittanut Sam007>>Javascript$W) palauta reppu($W, $wt, $val, $n - 1); // Palauta enintään kaksi tapausta: // (1) n. nimike sisältyy // (2) ei sisälly muuten return max($val[$n - 1] + knapSack($W - $wt[$n - 1] , $wt, $val, $n - 1), knapPack($W, $wt, $val, $n-1)); // Ohjainkoodi $profit = array(60, 100, 120); $paino = array(10, 20, 30); $W = 50; $n = määrä($voitto); echo knapSack($W, $paino, $voitto, $n); // Tämän koodin on toimittanut Sam007 ?>>>
Lähtö 220>
Aika monimutkaisuus: O(2N)
Aputila: O(N), pinotila tarvitaan rekursioon
Dynaaminen ohjelmointimenetelmä 0/1-reppuongelmaan
Muistiinpanon lähestymistapa 0/1-reppu-ongelmaan:
Huomautus: On huomattava, että yllä oleva rekursiota käyttävä funktio laskee samat osaongelmat uudestaan ja uudestaan. Katso seuraava rekursiopuu, K(1, 1) arvioidaan kahdesti.
Seuraavassa rekursiopuussa K() viittaa knapSack(). Seuraavassa rekursiopuussa näkyvät kaksi parametria ovat n ja W.
Rekursiopuu on tarkoitettu seuraaville näytetuloille.
paino[] = {1, 1, 1}, W = 2, voitto[] = {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)Rekursiopuu selkärepun kapasiteetille 2 yksikköä ja 3 kappaletta 1 painoyksikön painolla.
Koska sama osaongelma toistuu yhä uudelleen, voimme toteuttaa seuraavan idean ongelman ratkaisemiseksi.
Jos saamme aliongelman ensimmäistä kertaa, voimme ratkaista tämän ongelman luomalla 2-D-taulukon, joka voi tallentaa tietyn tilan (n, w). Jos nyt törmäämme samaan tilaan (n, w) uudelleen sen sijaan, että laskemme sen eksponentiaalisesti monimutkaisesti, voimme suoraan palauttaa sen tuloksen, joka on tallennettu taulukkoon vakioajassa.
java pää
Alla on yllä olevan lähestymistavan toteutus:
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) { // Tallenna funktiokutsun // pinon arvo taulukkoon ennen paluuta dp[index][W] = knapSackRec(W, wt, val, index - 1, dp); paluu dp[indeksi][W]; } else { // Tallenna arvo taulukkoon ennen palautusta dp[index][W] = max(val[index] + knapSackRec(W - wt[index], wt, val, index - 1, dp), knapSackRec(W , wt, val, indeksi - 1, dp)); // Taulukon palautusarvo tallennuksen jälkeen return dp[index][W]; } } int knapSack(int W, int wt[], int val[], int n) { // kaksoisosoitin //-taulukon ilmoittamiseksi dynaamisesti int** dp; dp = uusi int*[n]; // silmukka taulukon luomiseksi dynaamisesti kohteelle (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; } // Palauttaa suurimman voiton arvon static int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) W == 0) return 0; if (dp[n][W] != -1) palauttaa dp[n][W]; if (wt[n - 1]> W) // Tallenna funktiokutsun // pinon arvo taulukkoon ennen paluuta return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp); else // Taulukon palautusarvo tallennuksen jälkeen 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) { // Ilmoita taulukko dynaamisesti int dp[][] = new int[N + 1][W + 1]; // Silmukka täyttää // taulukon aluksi -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> 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] = reppu (wt, val, W, n-1) palauttaa t[n][W] # Kuljettajakoodi, jos __name__ == '__main__': voitto = [60, 100, 120] paino = [10, 20, 30] W = 50 n = len(voitto) # Alustamme matriisin aluksi arvolla -1. t = [[-1 i:lle alueella(W + 1)] j:lle alueella (n + 1)] print(reppu(paino, voitto, W, n)) # Tämän koodin on antanut Prosun Kumar Sarkar>'>C# // A utility function that returns // maximum of two integers function max(a, b) { return (a>b)? a: b; } // Palauttaa maksimihyötyfunktion arvon knapSackRec(W, wt, val, n,dp) // Perusehto if (n == 0 funktio knapSack( W, wt,val,N) { // Ilmoita dp-taulukko dynaamisesti // Intiaalisoi dp-taulukoita(riviä ja sarakkeita), joissa -1 alle 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 = voitto. pituus; ; console.log(knapSack(W, weight, profit, N)) // Tämän koodin tarjoaa akshitsaxenaa09
Lähtö Aika monimutkaisuus: O(N*W). Ylimääräisiä tilalaskelmia vältetään.
Aputila: O(N*W) + O(N). 2D-taulukkotietorakenteen käyttöä välitilojen ja O(N) apupinotilan (ASS) tallentamiseen on käytetty rekursiopinossa. Alhaalta ylös -lähestymistapa 0/1-reppu-ongelmaan:
Ratkaise ongelma noudattamalla alla olevaa ideaa:
Koska aliongelmat arvioidaan uudelleen, tällä ongelmalla on Overlapping Subproblems -ominaisuus. Joten 0/1-reppu-ongelmalla on molemmat ominaisuudet (katso Tämä ja Tämä ) dynaamisesta ohjelmointiongelmasta. Kuten muutkin tyypilliset Dynaamisen ohjelmoinnin (DP) ongelmat , samojen aliongelmien uudelleenlaskenta voidaan välttää rakentamalla väliaikainen taulukko K[][] alhaalta ylös -tavalla.
Kuva:
Alla on esimerkki yllä olevasta lähestymistavasta:
Antaa, paino[] = {1, 2, 3}, voitto[] = {10, 15, 40}, kapasiteetti = 6
- Jos mitään elementtiä ei täytetä, mahdollinen voitto on 0.
paino ⇢
tuote⇣/ 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 2 3
- Pussin ensimmäisen tuotteen täyttäminen: Jos noudatamme edellä mainittua menettelyä, taulukko näyttää seuraavalta.
paino ⇢
tuote⇣/ 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
- Toisen kohdan täyttäminen:
Kun jthWeight = 2, suurin mahdollinen voitto on max (10, DP[1][2-2] + 15) = max(10, 15) = 15.
Kun jthPaino = 3, suurin mahdollinen voitto on max(2 ei laita, 2 laitetaan pussiin) = max(DP[1][3], 15+DP[1][3-2]) = max(10, 25) = 25.
paino ⇢
tuote⇣/ 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 viisitoista 25 25 25 25 3
- Kolmannen kohdan täyttäminen:
Kun jthWeight = 3, suurin mahdollinen voitto on max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.
Kun jthPaino = 4, suurin mahdollinen voitto on max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.
Kun jthPaino = 5, suurin mahdollinen voitto on max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.
Kun jthPaino = 6, suurin mahdollinen voitto on max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
paino ⇢
tuote⇣/ 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 viisitoista 25 25 25 25 3 0 10 viisitoista 40 viisikymmentä 55 65
Alla on yllä olevan lähestymistavan toteutus:
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; } // Palauttaa maksimiarvon, joka // voidaan laittaa reppuun, jonka kapasiteetti on W int knapSack(int W, int wt[], int val[], int n) { int i, w; vektori> K(n + 1, vektori (W + 1)); // Rakenna taulukko K[][] alhaalta ylös -tavalle (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; } // Palauttaa maksimiarvon, joka // voidaan laittaa reppuun, jonka kapasiteetti on W int knapSack(int W, int wt[], int val[], int n) { int i, w; int K[n + 1][W + 1]; // Rakenna taulukko K[][] alhaalta ylös -tavalle (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; } // Palauttaa maksimiarvon, joka // voidaan laittaa reppuun, jonka kapasiteetti on W static int knapSack(int W, int wt[], int val[], int n) { int i, w; int K[][] = uusi int[n + 1][W + 1]; // Rakenna taulukko K[][] alhaalta ylös -tavalle (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; } // Palauttaa maksimiarvon, joka // voidaan laittaa reppuun, jonka // kapasiteetti on W static int knapSack(int W, int[] wt, int[] val, int n) { int i, w; int[, ] K = uusi int[n + 1, W + 1]; // Rakenna taulukko K[][] alhaalta // ylöspäin tapaukselle (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; } // Palauttaa maksimiarvon, joka voidaan // laittaa reppuun, jonka kapasiteetti on W funktio knapSack(W, wt, val, n) { let i, w; olkoon K = uusi Joukko(n + 1); // Rakenna taulukko K[][] alhaalta ylös -tavalle (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. ?>>>
Lähtö Aika monimutkaisuus: O(N*W). missä 'N' on elementtien lukumäärä ja 'W' on kapasiteetti.
Aputila: O(N*W). 2D-taulukon käyttö, jonka koko on 'N*W'.verilog-tapauslausunto
Tilaoptimoitu lähestymistapa 0/1-reppu-ongelmaan dynaamisen ohjelmoinnin avulla:
Ratkaise ongelma noudattamalla alla olevaa ideaa:
dp[]-taulukon nykyisen rivin laskemiseen tarvitaan vain edellinen rivi, mutta jos aloitamme rivien poikkimisen oikealta vasemmalle, se voidaan tehdä vain yhdellä rivillä
Alla on yllä olevan lähestymistavan toteutus:
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>
Lähtö Aika monimutkaisuus : O(N*W). Ylimääräisiä tilalaskelmia vältetään
Aputila : O(W) Koska käytämme 1-D-taulukkoa 2-D-taulukon sijaan