Dynamic Programming😎

Navneet KumarNavneet Kumar
19 min read

Dynamic Programming = mai hu DP (Ha ha wahi jis se sabko dar lagta hai πŸ’€ par ab darne ki zarurat nahi, mai itna bada saari badi company ka favorite topic hu 😎) **par mai bahut kaam ka hu to apna dar kam karne ke liye mai aapko poori detail mein bataunga ke kaam kaise karta hu, kya hu mai aur baaki sab is pure journey mein bataunga mai ok abhi daro mat πŸ’€ samjho mujhe tumhare us EX😨😨😱 se to accha hu mai uske tarah thoda toxic to par accha wala to chalo ab hum start karte hai (bolo Radhe Radhe πŸ™‡πŸ»πŸ™‡πŸ»β€β™€οΈ)

Aur ek baat aur mere saath chalne se pehle mera ek chhota bhai hai agar aap usko thoda acche se dekh loge to accha hoga uska naam hai (Recursion❀️) bahut accha bade bade code ko bahut chhota kar deta usko aap thoda acche se padh lena ek baar

To pehle pehle mere andar kya kya hai ye dekha mai darna nahi chahta hu pehle aap hum se mil lo ke dekhta kaisa. Agar mai dekh jau to mujhe dekh kar aap jaan paoge mai DP hu ok.

IDENTIFYπŸ˜‰

1 = DP = Enhanced recursion, 2 = optimal
AB question kaise pata lagaye ke ye Enhanced recursion or Enhanced DP hai
to. A = Choice => matlab hamko bahut saari ya choice de rakhi hogi (jaise ek bag hai aur uske paas 2 ball hai to aapke paas hoti hai choice ke le ya na le πŸ”΄ ya jab aapke paas aapke bande ya bandi se accha option hota hai choice hoti hai na ke usko jeevan mein rakhe ya na rakhe choice milti hai na)
B => Dekho agar choice de rakhi hai to recursion lagega aur overlapping problem hai to DP lagegi (Ab overlapping kya hoti aayenge baad mein abhi sun lo bas)

Chalo upar upar se bata deta hu Recursion do baar call ho raha ho to DP lagega aur ek baar ho raha ho to nahi lagega par 2 baar ho raha hoga to lagega hi most aur chance hai lagega hi

2 Optimal = matlb min , max ya or bhi aage dekhte hai ok

To ab tumko dekh gaya ke multiple option hai to ab kya karoge samjh DP lagegi kaise lagegi ye pata nahi hoga na haan bahut se log honge jo (Top down) laga kar matrix fill karna start kar denge fir bolenge DP hard hai

nahi bro simple method hai ok
Recursionβ€”> Memorize β€”> Top down

Starting ke kuch most important problem hai ham ab sab kuch problem se learn karenge aur mai har problem ko explain karunga aur uske leetcode ke link dunga aur usko aap khud solve karoge jo padha uske base pe πŸ˜‰πŸ˜‰πŸ˜‰πŸ˜‰

0-1 knapsack (6), Unbounded knapsack (5), Fibonacci (7), LCS (15), LIS (10), Kadane's Algorithm (6), Matrix chain Multiplication (7), DP on Trees (4), DP on Grid (14)

ye hi DP hai bas inke variations hai inko kar le acche se around (80) problem hai jo solve kar sakte hai ham in question karne ke baad tum saare DP ke question laga paoge 100% (agar sahi se padha hoga)

To ab ham chapert 2 starte karege πŸ˜‰( To isame ham pata lagaege ke kuapsack ke 6 most important perblom hai vo kon se hai 😎😎 )To shru karte bina kise bakvass ke ❀️❀️

Subset Sum

  1. Equal Sum Partition

  2. Count of Subset Sum

  3. Minimum Subset Sum Difference

  4. Target Sum

  5. Number of Subsets with Given Difference

In saare problems ke baad aapko kisi bhi tarah ki problem nahi hogi ok

Jab hum pehli problem karenge tab uske baad saare code mein thoda minor sa change karna hoga aur aap log saare questions kar sakte hai aur in case koi new 7th problem aa jaye to vo nahi nahi ke inko karke dimaag itna aa jayega ke hum vo aaram se kar sakte hai vo ok.

To is sabko padhen se pehle hum 0-1 Knapsack problem.

What is 0-1 Knapsack problem? 🀷🏻

Ye in saare important questions ka base case matlab is se saare coding ke problems solve hongi ok isko dhyan se samajhna jab aap isko samajhna start karoge to aapne aap sab samajh mein aane lagega ok aur mai tum easy lagne lagunga ok (mujhe bhul gaye mai DPπŸ’€)

Three types mein dekhta hu ok:
a. Fractional Knapsack β€”β†’ Greedy
b. 0/1 Knapsack
c. Unbounded Knapsack

To haan bahut knapsack knapsack knapsack hota kya hai ye pehle to batao DP bhai πŸ™‡πŸ» OK

To simple language mein batata hu mai just imagine ke ek bag hai tumhare paas ok ab usme tum minimum number of items daal sakte ho (item ka matlab koi bhi object jaise banana, koi weight etc aur uski value bhi dekhte hai hum ok)

int[] weights = {1, 3, 4, 5};
int[] values  = {10, 40, 50, 70};
int W = 7

Jaise aap dekh sakte hai isme humare paas do weight hai ok first one is weights aur unki value bhi dekh rahi hogi uske hisab se hum weight dalenge (I know nahi samajh aaya tumko dekho)

     ___________
    /           \
   |     w       |
   |     V       | ------> BEG HAI YE BHAI/BEHAN
   |             |
    \___________/
To jaise aap dekh sakte ho ek bag hai ok uske andar to jaise aap log dekh sakte hai ke 
isme hum 7 weights tak hi daal sakte hai bas aur aise weights dalna hai ke hum max value 
la sake (kaun sa aisa weight pick kare humko profit max ho)
Example 1: Jaise upar jo example hai usse hum bas index (1,2) lenge to max
 profit aayega ok ---> 40+50=90
 aur koi bhi weight nahi hai jis se humko 90 se zyada profit ho jaye ok

To abhi aap log mere first roop ko dekhoge jisko hum Fractional Knapsack bolate hai isme humko DP ki need nahi hogi hum isko Greedy ka use karke bana sakte hai hum (kyunki hum chahe to puri value le ya half bhi sakte jaise max weight ko 7 le sakte hai to max profit ke liye hum kisi ka half part bhi le sakte hai πŸ₯ΈπŸ₯Έ)

To ab meri baat karte hai ke kaise kya karna DP mera kaha use hai mera use hai knapsack mein πŸ”΄πŸ”΄

Like mujhe ya pura daalo ya fir daal hi mat like max value 7 hai aur mujh mein 6 aa chuka hai par 1 baki hai aur mujhe 1 pura hi daalna hoga mai half nahi daal sakta hu ok ya use hota hai mera pura.

1: subset Sum

2:Equal sum partition
3:Count of subset sum
4 Minimum subset sum Diff
5: Target Sum
6: Number Of subset given difference

To in saare problems ke baad aapko kisi bhi tarah ki problem nahi hogi ok.

Jab hum pehli problem karenge tab uske baad saare code mein thoda minor sa change karna hoga aur aap log saare questions kar sakte hai aur in case koi new 7th problem aa jaye to vo nahi nahi ke inko karke dimaag itna aa jayega ke hum vo aaram se kar sakte hai vo ok

To is sabko padhen se pehle hum 0-1 Knapsack problem.

     ___________
    /           \
   |     w       |
   |     V       | ------> BEG HAI YE BHAI/BEHAN
   |             |
    \___________/
 to jasa aap dekh sakte ho  ek beg hai ok uske ander  to jasa aap log dekh 
sakte hai ke isame ham 7 weights tak hee daal sakte hai bas or aase weights 
dalana hai ke ham max value la sake(kon sa aasa weights  pick kare hamko 
profit max ho )

example 1: JASE uper jo examle hai usa se ham bas index (1,2) lenge to max
profit aayega ok --->40+50=90 
or koi bhi weights nahi hai jis sa se hamko 90 se jada profit ho jaye ok

To abhi aap log mere frist roop ko dekhoge jisko ham Fractionaln kuapsack bolate hai isame hamko DP ke need nahi hogi ham isko Greedy ka use karke bana sakte hai ham (kuki ham chahe to puri value le ya half bhi sakte jase max weight ko 7 le sakte hai to max profit ke leye ham kise ka half part bhi le sakte haiπŸ₯ΈπŸ₯Έ )

To ab meri baat karte hai ke kase kay karna DP mera kaha use hai mera use hai knapsack mai πŸ”΄πŸ”΄

like mujhe ya pura daloo ya fir daal hee mat like max valaue 7 hai or mujh mai 6 aa chuka hai per 1 baki hai or mujhe 1 pura hee dalna hoga mai half nahi daal sakta hu ok ya use hota hao mmera pura

javaCopyEditint[] weights = {1, 3, 4, 5};
int[] values  = {10, 40, 50, 70};
int W = 7; 
Qusetion=> TO seen ye hai ke hamko aase weigth pick karne jinke value max aaye 
maatlb profit max aaye 
EAX: index 1,2 per profit max aayga ok

TO ham pata kaise lagayenge ke knapsack ya hamko DP lagani hai to dekho ye kuch simple hints dega jaise choice aur optimal code likhne ko bolega


1.Choice: Ye tab hota hai jab aapke paas weight ko select karne ki choice hoti hai. Aapko check karna hota hai ki kaunsa weight lena hai ya nahi.

2.Optimal: Iska matlab hota hai maximum ya minimum nikalna, jaise maximum profit ya minimum cost.

To isme kaha ye sab? => Ye raha hamare weight ko select karne ki choice hai, 1 check βœ… + max profit (aur tumne dhyan se padha ho to maine bataya optimal ka matlab ke max nikalna, min, etc.) to ye second βœ… ye pehchaan iske.

DP: Recursion β€”β€”β€”β†’ Memoization β€”β€”β€”β†’ Top-Down (DP) main part jo ham karenge.

To this is a Knapsack Recursive(yaha se main maal ayega πŸ˜ŽπŸ˜‰)

stpe one is a =>🌳 Choice Tree (Include / Exclude Diagram)

                 W = 3, i = 0

                [i=0, W=3]
               /           \
         Includeβœ…         Exclude🚫
          /                  \
[i=1, W=2, val=10]       [i=1, W=3, val=0]
     /       \               /       \
  Inc        Exc         Inc        Exc
  /           \            \          \
[i=2,W=-1]  [i=2,W=2]   [i=2,W=0]   [i=2,W=3]
 val=?       val=?       val=?       val=?

To ye choice diagram de rakha hai to isko dekho ham 2 choice hai jase ham 
select kar skate hai or nahi kar sakte (jis se pata chlata hia ke ye DP ka 
dono point aayege ok)

Generated image

ye dekho choice diagram hai ye important hai ok isko bana liya to half kaam ho jayega ok (mai tumhare bas mein aane start ho jaunga aur tumhara dost ban jaunga ok)

to ye hai first function hai ok dhyan se dekho ye mera base part hai ok aa aayega to bahut aasani hogi mujhe samajhne mein ok πŸ₯ΈπŸ₯ΈπŸ₯ΈπŸ₯Έ

int Knapsack(int wt[], int val[], int w, int n){
// to ab important step hai first is a BASE CASE (BC => kaise dekhe ab ye question aata hai? Base Condition β€”β€”β€”β€”> Think of the smallest valid I/P)
to valid input kya hoga dekho sabse chhota lenge hum jaise humko aage need hogi to vo dono array ko mila kar hum n=0; aur W = 0 lenge sabse chhota aur valid kya hi ho sakta hai bro vo hi hoga)

if(n==0 || w==0) return 0 // BC => kyunki sabse chhota choose karna hai humko ok aur ye jaruri hai bag lekar jaoge sabse kam kya hi daloge usme Zero bas us se kam hi daloge

//choice diagram => To iske condition likhte hai ye hamari first condition hai aur vo jab aayegi jab hum weight select karenge ok else wali jab jab hum select nahi karenge 🚫

if(wt[n-1]<=w)
return max(val[n-1]+
Knapsack(wt,val, w-wt[n-1], n-1),Knapsack(wt,val,w,n-1);
else(wt[n-1]>w) return Knapsack(wt, val,w,n-1)

}

βœ… 1. Java Version

javaCopy codepublic class Knapsack {
    public static int knapsack(int[] wt, int[] val, int W, int n) {
        if (n == 0 || W == 0) return 0;

        if (wt[n - 1] <= W) {
            return t[n][w]= Math.max(
                val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1),
                knapsack(wt, val, W, n - 1)
            );
        } else {
            return t[n][w] knapsack(wt, val, W, n - 1);
        }
    }

    public static void main(String[] args) {
        int[] weights = {1, 2, 3};
        int[] values = {10, 15, 40};
        int W = 6;
        int n = values.length;
        System.out.println("Maximum profit is: " + knapsack(weights, values, W, n));
    }
}

βœ… 2. C++ Version

cppCopy code#include <iostream>
#include <algorithm>
using namespace std;

int knapsack(int wt[], int val[], int W, int n) {
    if (n == 0 || W == 0) return 0;

    if (wt[n - 1] <= W) {
        return max(
            val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1),
            knapsack(wt, val, W, n - 1)
        );
    } else {
        return knapsack(wt, val, W, n - 1);
    }
}

int main() {
    int wt[] = {1, 2, 3};
    int val[] = {10, 15, 40};
    int W = 6;
    int n = sizeof(val) / sizeof(val[0]);
    cout << "Maximum profit is: " << knapsack(wt, val, W, n) << endl;
    return 0;
}

βœ… 3. Python Version

pythonCopy codedef knapsack(wt, val, W, n):
    if n == 0 or W == 0:
        return 0

    if wt[n-1] <= W:
        return max(
            val[n-1] + knapsack(wt, val, W - wt[n-1], n-1),
            knapsack(wt, val, W, n-1)
        )
    else:
        return knapsack(wt, val, W, n-1)

weights = [1, 2, 3]
values = [10, 15, 40]
W = 6
n = len(values)
print("Maximum profit is:", knapsack(weights, values, W, n))

HELLOW JI TO YE DAY TWO HAMARE DP KA PATH KA HAM AB RECURSION VERSION PADHNGE HAM OK TO START KARTE HAI😎😎(BOLO RADHE RADHEπŸ™‡πŸ»πŸ™‡πŸ»πŸ™‡πŸ»πŸ™‡πŸ»)

Ab ham recursion ko Memoize mai convert karnege ok to ab

to seen aasa hai ke kuch chnage ho rahe hai kuch nahi ab dekho agr tum function se ye compare karo to
if (wt[n - 1] <= W) { return Math.max( val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1), knapsack(wt, val, W, n - 1) );
isame value[] arr ko dekho vo chnage nahi ho raha or wt [] arr bhi change nahi ho raha hai to change kay ho raha hai fir jo hamata int w wali value or int n wali to memo (Memoization) ke leye hamko vase metrix cretate karni jo chnage hp rahi hai
to jo bhi bhi chnange ho raha uski matrix banayye or puri matix mai -1 fill kar denge
πŸ“Š DP Table (Initial: All -1)

plaintextCopy code        Capacity β†’
        0    1    2    3    4
Items +-------------------------
  0   | -1  -1   -1   -1   -1
  1   | -1  -1   -1   -1   -1
  2   | -1  -1   -1   -1   -1
  3   | -1  -1   -1   -1   -1

to koi bhi value nekalane hogi to mai pehle dekhuga waha per vo valaue prenst hai ke nahi hai to pura recursion function call karne ke need nahi bas dekho waha hai ke nahi or age -1 dekhuga or nahi hai to waha per usko relce kar dunga or dekhuga ke us jagha per like(3,2 ) w=3 Thred row,or n= 2 second col, agr kuch huaa -1 ke alava to mai retun kar dunag nahi huaa to waha per recursion call karuga or waha jo value hai unki help se new value stre kar dunga or jis aage nedd ho to return kar sake

Memoization mein yeh base case:

if(n == 0 || W == 0) return 0;
βœ… Initialization in Memoization (Conceptual Visualization)
        Capacity β†’
       0   1   2   3   4
Items +-------------------
  0   | 0   0   0   0   0   ← (n == 0) β†’ no items = 0 profit
  1   | 0   ?   ?   ?   ?
  2   | 0   ?   ?   ?   ?
  3   | 0   ?   ?   ?   ?

To ab kay chnage kare ke hamaa Recurestion wala code ko ham Memoization
mai convert kar sake to

FRIST STEP(ham ab kay constrian ko dekh lenge or uske hisab se ek new dp bana lenge or usko top per banayege or unko static banayege taki sab accessble ho ok
To = int static t[102][1002] ye ham constrain dekh kar bana rahe hai ok to ye code kasa dekhyegga

int static t[102][1002];
memset(t,-1,sizeof(t))

second step ( Ham ab ye karege ke base to same rahega per uske uske baad ham ye line add karege like
if(t[n][w]β‰ -1) return t[n][w];
is se kay jo call lag rahi pehle ke code 01Knapsack wale mai flatu mai vo nahi lagega to ye chheck karga ke value save hai agr nahi hai to ye karege ham

Thred step
jo mani tha na code max wala
if (wt[n - 1] <= W) { return t[n][w]= Math.max( val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1), knapsack(wt, val, W, n - 1) ); }
} else {

return t[n][w] =knapsack(wt, val, W, n - 1);
}
to kay huaa hamne bas t[n][w] ko hee add keay ku keya kuki hamko vo to matrix khali thi usko fill karna tha waha se -1 hata kar jo ki falatu call na lage

To full code ye raha

βœ… Corrected + Memoized 0/1 Knapsack Code in Java

javaCopy codepublic class Knapsack {

    // Step 1: Static DP array based on constraints
    static int[][] t = new int[102][1002];

    public static int knapsack(int[] wt, int[] val, int W, int n) {
        // Base case
        if (n == 0 || W == 0) return 0;

        // Step 2: Memoization check
        if (t[n][W] != -1) return t[n][W];

        // Step 3: Choice diagram with memoization
        if (wt[n - 1] <= W) {
            return t[n][W] = Math.max(
                val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1),
                knapsack(wt, val, W, n - 1)
            );
        } else {
            return t[n][W] = knapsack(wt, val, W, n - 1);
        }
    }

    public static void main(String[] args) {
        int[] weights = {1, 2, 3};
        int[] values = {10, 15, 40};
        int W = 6;
        int n = values.length;

        // Step 1.5: Initialize t with -1
        for (int i = 0; i < 102; i++) {
            for (int j = 0; j < 1002; j++) {
                t[i][j] = -1;
            }
        }

        System.out.println("Maximum profit is: " + knapsack(weights, values, W, n));
    }
}

βœ… 1. C++ Version (Memoization)

cppCopy code#include <iostream>
#include <cstring>
using namespace std;

// Step 1: DP table
int t[102][1002];

int knapsack(int wt[], int val[], int W, int n) {
    // Base case
    if (n == 0 || W == 0) return 0;

    // Step 2: Memoization check
    if (t[n][W] != -1) return t[n][W];

    // Step 3: Choice logic
    if (wt[n - 1] <= W) {
        return t[n][W] = max(
            val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1),
            knapsack(wt, val, W, n - 1)
        );
    } else {
        return t[n][W] = knapsack(wt, val, W, n - 1);
    }
}

int main() {
    int wt[] = {1, 2, 3};
    int val[] = {10, 15, 40};
    int W = 6;
    int n = sizeof(val) / sizeof(val[0]);

    // Step 1.5: Initialize t with -1
    memset(t, -1, sizeof(t));

    cout << "Maximum profit is: " << knapsack(wt, val, W, n) << endl;
    return 0;
}

βœ… 2. Python Version (Memoization)

pythonCopy code# Step 1: Create DP table
t = [[-1 for _ in range(1002)] for _ in range(102)]

def knapsack(wt, val, W, n):
    # Base case
    if n == 0 or W == 0:
        return 0

    # Step 2: Memoization check
    if t[n][W] != -1:
        return t[n][W]

    # Step 3: Choice logic
    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)
        )
    else:
        t[n][W] = knapsack(wt, val, W, n - 1)

    return t[n][W]

# Inputs
wt = [1, 2, 3]
val = [10, 15, 40]
W = 6
n = len(val)

print("Maximum profit is:", knapsack(wt, val, W, n))

DP :Top Down DP

Top Down DP: iskani need kay padhi ku use karte hai jab ham recurion se kar rahe the sab kuch to need kay padhi

To need ye hai ke jab ham bahut jada hee resusive call use karte hai to to hamara stack uper tak bhar jata hai fir uske baad or resursion kaam nahi aata hai
to ham Top Down DP ka use karte hai
To step kay hunge
step 1 = Initialize karna hota hai
step 2 = Reverese call funcn ne
wt[]= [1,3,4,5]
val [] = [1,4,5,7]
w =7
t[n+1][w+1] = t[5][8]
ab ham matrix banayegi ok 5,8 ke
πŸ“Š Final Matrix Size:

i ↓ / w β†’01234567
000000000
1
2
3
4

Hum ye matrix bharte jayenge row-wise, left to right

i ↓ / w β†’01234567
000000000
101111111
201145555
301145669
401145789

🎯 Final Answer: t[4][7] = 9

That means: maximum value you can achieve in weight 7 = 9

to ye 9 hai ye last mai aaya to max profit hamko ye 9 milega 4,7 index per aap diagram mai dkeh sakte hai (or ab soch rahe hoge ke ye jo bolate hia sub perblom mai divied ho jata hai kase hota hai ku hota hai to iska ans ye hai

ke jab ham kise bhi index per jata hai to like[5][2] to ye to isko mai sub perblom mai baat leya ab usko slove karege or ham ko vpas jane ke need nahi hoto hai usko ag slove kar rakha hoga to to value hogi nahi kar rakha hoga -1 rahega jis se pta rahe ke vo index slove nahi huee hai

to ab code ke bari
for(int i=0;i<n+1;i++){
for(int j=0;j<n+1;j++)
if(i==0|| j==0) t[i][j]=0;
}

step2
jo jo function chnage ho raha hai waha per ham t la dnage ok
if(wt[n-1]<=w){
t[n][w] = max(val[n-1] + t[w-wt[n-1], [n-1]], t[n-1] [w]);
}else
t[n][w] = t[n-1][w]

πŸ’» Java Code

public class KnapsackTopDown {
    public static void main(String[] args) {
        int wt[] = {1, 3, 4, 5};
        int val[] = {1, 4, 5, 7};
        int W = 7;
        int n = wt.length;

        int[][] t = new int[n + 1][W + 1];

        // Step 1: Initialization
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= W; j++) {
                if (i == 0 || j == 0) {
                    t[i][j] = 0;
                }
            }
        }

        // Step 2: Filling the table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= W; j++) {
                if (wt[i - 1] <= j) {
                    t[i][j] = Math.max(val[i - 1] + t[i - 1][j - wt[i - 1]], t[i - 1][j]);
                } else {
                    t[i][j] = t[i - 1][j];
                }
            }
        }

        System.out.println("Maximum profit: " + t[n][W]);
    }
}

πŸ’» C++ Code

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int wt[] = {1, 3, 4, 5};
    int val[] = {1, 4, 5, 7};
    int W = 7;
    int n = sizeof(wt) / sizeof(wt[0]);

    vector<vector<int>> t(n + 1, vector<int>(W + 1, 0));

    // Filling the table
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                t[i][w] = max(val[i - 1] + t[i - 1][w - wt[i - 1]], t[i - 1][w]);
            } else {
                t[i][w] = t[i - 1][w];
            }
        }
    }

    cout << "Maximum profit: " << t[n][W] << endl;
    return 0;
}

πŸ’» Python Code

wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
W = 7
n = len(wt)

# Initialize matrix
t = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

# Fill the matrix
for i in range(1, n + 1):
    for w in range(1, W + 1):
        if wt[i - 1] <= w:
            t[i][w] = max(val[i - 1] + t[i - 1][w - wt[i - 1]], t[i - 1][w])
        else:
            t[i][w] = t[i - 1][w]

print("Maximum profit:", t[n][W])

🧠 Output:

yamlCopy codeMaximum profit: 9

To ab ham ab vo 6 perblom start karege ok 😎😎πŸ”₯πŸ”₯

0
Subscribe to my newsletter

Read articles from Navneet Kumar directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

Navneet Kumar
Navneet Kumar