01 Knapsack Tabulation Dynamic Programming | How to build DP table

Поделиться
HTML-код
  • Опубликовано: 9 янв 2025

Комментарии • 98

  • @sakthim7160
    @sakthim7160 4 года назад +90

    dp[i][j]= max( dp[i-1][j], profit[i-1]+dp[i-1][*j*-wt[i-1] ) you specified W instead of j while including the element in final else statement.

    • @techdose4u
      @techdose4u  4 года назад +18

      Yea right. It should be j.

    • @amitkumargupta6722
      @amitkumargupta6722 4 года назад +17

      @@techdose4u Its okay...concepts are more important than code..

    • @Nieobliczalny1000
      @Nieobliczalny1000 Год назад

      @@techdose4u What if j i wt[i-1] will be smaller than 0? Generally index out of bound?

    • @savostyanov
      @savostyanov Год назад

      ​@@Nieobliczalny1000 We prevent this case in this line if (i == 0 or j == 0) dp[i][j] = 0

    • @JitendraSingh-qd7jk
      @JitendraSingh-qd7jk Год назад

      Stop copying and pinning aditya verma's code Sakthim

  • @vend57
    @vend57 4 года назад +39

    saw an algoexpert ad before the video. Am I buying that course after knowing that Techdose has covered 5 X more problems than Algoexpert ?

  • @bhargavsai2449
    @bhargavsai2449 3 года назад +11

    within 2 or 3 yrs you will have millions of subscribers, great channel.

  • @MohamedSayed-wl5cj
    @MohamedSayed-wl5cj 4 года назад +3

    Best video on RUclips explains Knapsack problem with clear way,thanks

  • @dhananjaychoudhary7836
    @dhananjaychoudhary7836 4 года назад +16

    Thanks a lot man.
    This is my 4th attempt to understand knapsack DP and also the last one.

  • @34_harshdeepraghuwanshi98
    @34_harshdeepraghuwanshi98 4 года назад +13

    Sir your explanation is too much above from paid courses and also in your video i never get a doubt or if i get then you always cleared doubt by yourself later in video thanks a alot sir for providing free quality education 🙏🙏👍👍👍👍👍

  • @theghostwhowalk
    @theghostwhowalk 4 года назад +9

    Never knew about heap Vs Stack memory thanks much for in-depth explanation!

  • @aryankumar87771
    @aryankumar87771 4 года назад +2

    the sheer clarity of the explanation

  • @dionisorules
    @dionisorules 2 года назад +2

    Thanks for presenting this problem so orderly, going from the decision making tree, to the recursive approach to end up translating that into the tabular iterative approach. Now this is no more black magic for me, but step by step sound reasoning. Like others said your capacity to explain these complex solutions is just brilliant and far superior to paid courses.👏🏼👏🏼👏🏼

  • @ismail8973
    @ismail8973 3 года назад +2

    Your intuition explanation is on another level

  • @mikekibet1786
    @mikekibet1786 3 года назад +13

    Another masterful explanation. If I could subscribe twice, I would.

  • @vaibhavkumargautam
    @vaibhavkumargautam 2 года назад

    This is the best explanation i ever came across..

  • @sorajkandari9603
    @sorajkandari9603 3 года назад

    How can u be so clear in every single word u say. awesome bro !!

  • @gowthamsankaran67
    @gowthamsankaran67 7 месяцев назад

    Thank you so much for the explanation. I was struggling with converting recursive to iterative code. This helped me a lot.

  • @mallikarjunareddy4848
    @mallikarjunareddy4848 3 года назад +1

    Thanks for the explanation. It gives me an idea on how to come up with bottom up solution for dp problems . It would have been great if you had covered why we are considering items from right to left. I sat for couple of hours thinking about it and finally, I could understand the benefit of considering items from right to left over left to right

    • @niksgupta36
      @niksgupta36 3 года назад

      Can you mention those here?
      I think he sorted the profit array in increasing, hence working from right to left.

  • @salilkumar6500
    @salilkumar6500 3 года назад

    Your explanation is crisp,clear n short. Very helpful to me . Keep the good work going on man,

  • @prathamanand1037
    @prathamanand1037 3 года назад +2

    this was a bomb video, better than everything I have ever seen

  • @ashvinimeshram5242
    @ashvinimeshram5242 3 года назад +2

    Your alll vedios are really nice.and it help me alot in my concept buliding thank u so much🙏🙏🙏🙏really good content

  • @pradnyamahadik5540
    @pradnyamahadik5540 8 месяцев назад

    Wow...really amazing explanation💯

  • @mahendrasuthar7354
    @mahendrasuthar7354 3 года назад

    amazing bhai kya samjhaate ho mjaa aa gya thanks a lot.

  • @dhanashreegodase4445
    @dhanashreegodase4445 3 года назад +1

    best video i have ever seeen..excellent..thanks alot

  • @sarvarjuraev1376
    @sarvarjuraev1376 2 года назад

    Thank you very much for the accurate explanation.

  • @vigneshvicki7020
    @vigneshvicki7020 2 года назад +1

    i almost gave up trying to understand DP in tabulation, but Finally I did understand, Thank you very much bro🥹

  • @namanvijay3514
    @namanvijay3514 3 года назад +2

    great series , following this one 👍

  • @jayanthjj
    @jayanthjj 3 года назад +1

    Thanks for this Great Video series!

  • @codingexception6502
    @codingexception6502 3 года назад

    Your explanation is really good.

  • @nimishkumar9779
    @nimishkumar9779 4 года назад +2

    Thanks a lot! The best explanation.

  • @garimakumari4346
    @garimakumari4346 3 года назад +1

    woow man really great..nice job

  • @Neonb88
    @Neonb88 2 года назад

    Wait his handwriting on a computer is so pretty. That's just the first thing I noticed. Obviously it's a good tutorial video, too

  • @samarasimhachalla3509
    @samarasimhachalla3509 3 года назад +1

    When deciding about which one to go ahead with Memoization or Tabulation methods. Try to identify the no.of values in the DP table or array that is required to solve the problem. If the number is very less compared to the total size, then go ahead with Memoization for better time complexity because in the Tabulation method it'll compute the whole table, then give you the output. And yeah, if the number of values that need to be computed in the table or array, is not very small when compared to the total size, then yeah go ahead with tabulation.
    Credits: GFG

  • @debdattabiswas4902
    @debdattabiswas4902 2 года назад

    excellent explaination.

  • @大盗江南
    @大盗江南 7 месяцев назад

    amazing video, thank u

  • @MadForCs16
    @MadForCs16 4 года назад +5

    Hello sir, I have one doubt, in this process we're actually moving from bottom to up ....like n=0, W=0. then why are we calling it *top-down* approach? It should be called *bottom-up*

    • @techdose4u
      @techdose4u  4 года назад +4

      You are right. I had made a community post regarding this. Wish you were there 😅 But yea, it's bottom up.

  • @nknidhi321
    @nknidhi321 3 года назад +2

    Thank you..🙏❤️

  • @adim1212
    @adim1212 3 года назад +2

    You and Aditya Verma both have explained DP thoroughly and both have messed up at same concept i.e. Mistaken Bottom-Up as a Top-Down approach. Did both of you shared same notes or what???

    • @hiteshchopra9181
      @hiteshchopra9181 3 года назад

      Bro I was literally finding the same in comments as I was also confused haha. But no doubt both of them teach very very good.

  • @srikantsharma6430
    @srikantsharma6430 4 года назад +1

    Well explained!

  • @abhigyansharma9108
    @abhigyansharma9108 3 года назад +1

    Love You Sir

  • @ankitparashar8730
    @ankitparashar8730 3 года назад +1

    I have solved most of dp problem using recursion and memoization .i felt memoization dp is easier than tabalization .
    Should I learn tabalization dp ???

  • @venkatadokku9190
    @venkatadokku9190 4 года назад +1

    Nice share. Can you point some questions associated with this concept ? Appreciated.

  • @rangapavankumar79
    @rangapavankumar79 4 года назад +3

    How come 'w' in last line is it 'j' b'coz 'j' is capacity of bag?

    • @techdose4u
      @techdose4u  4 года назад +3

      It will be j because j is current capacity.

  • @KhushiYadav-fo9ul
    @KhushiYadav-fo9ul Год назад +1

    Please correct me if I am wrong , the memoization is a top- down approach and tabulation is a bottom up approach .....

    • @techdose4u
      @techdose4u  Год назад

      While it looks just the opposite but you are correct :)

  • @rishviks8987
    @rishviks8987 4 года назад +2

    Sir I'm good at memoisation but I don't have any idea about tabulation coz I nerver used it. Should one know both of them?

  • @naman_goyal
    @naman_goyal 4 года назад +1

    Very nice

  • @adityaojha2701
    @adityaojha2701 3 года назад +1

    We start filling table from smaller value to greater value, so this become bottom up approch. Am I right??

    • @Rasheed21
      @Rasheed21 8 месяцев назад

      Not really. Tabulation/Iteration is Bottom-Up even if you interate in decreasing order. Recursivion+Memoization is Top-Down even if your recusion is in increasing order.

  • @imukai
    @imukai 2 года назад

    I get that this method gives you the total profit at the end of the table -- but how do you determine which of the elements in the set were selected to arrive at that sum?

    • @smitkarwatkar03
      @smitkarwatkar03 Год назад

      use a prev array which will store the indexes of each optimal step. at the end you would get all the elements in your optimal solution

  • @kuntipatidar5191
    @kuntipatidar5191 4 года назад +1

    how your concepts are so strong?

    • @priyank907
      @priyank907 4 года назад +3

      Patience and practice

  • @heedererroger9324
    @heedererroger9324 4 года назад

    your approach to get maximum value is direction which is from right to left. But your table structure is left-top to right bottom to find maximum value.
    It's confusing... am I misunderstanding?

  • @santoshr4212
    @santoshr4212 2 года назад

    Friends, can someone explain in which case memoization will be useful because unlike Fibonacci I dont see a case where same value/computation can be repeated because in each case weight may be different

  • @amansingh.h716
    @amansingh.h716 3 года назад +1

    THANKS SIR

  • @biswajitghosh9315
    @biswajitghosh9315 4 года назад

    Love you bro

  • @Cloud-577
    @Cloud-577 2 года назад

    Thank you

  • @manoranjaniiit
    @manoranjaniiit 4 года назад +1

    too good

  • @piyushkumar-wg8cv
    @piyushkumar-wg8cv 2 года назад

    You have messed up the indexes.

  • @_SajjadHossainTalukder
    @_SajjadHossainTalukder 3 года назад

    A bottom-up algorithm "starts from the beginning," while a recursive algorithm often "starts from the end and works backwards" . That's why recursive algorithm is known as top down .
    U wrongly interpreted this top down Approach. It may be Bottom-Up approach. Please Make it clear.

  • @tech_wizard9315
    @tech_wizard9315 4 года назад

    Please make a roadmap for fresher to crack google in 6months

  • @andresdallarizza1526
    @andresdallarizza1526 6 месяцев назад

    fucking legend
    lov u
    adore u

  • @learnersparadise7492
    @learnersparadise7492 3 года назад +1

    You copy pasted content of Mr Aditya Verma in English, just...even his calling of bottom up as top down is copied man....do some original work please 🥺🥺

  • @tvrao123
    @tvrao123 4 года назад +1

    too lengthy explanation

    • @techdose4u
      @techdose4u  4 года назад +2

      It was basics so it went long.

    • @Dryicicles
      @Dryicicles 4 года назад +2

      lmao then shut up and dont learn

  • @manishkumartyagi1815
    @manishkumartyagi1815 4 года назад +1

    Looks like copied from the videos of Aditya Verma :D , exactly same.......... hahahahahaha