Ahh, the magic of recursion. I struggled with the explenation a bit, but I think i get it now. But like you said, it's a very slow solution so we need to do better. It makes a lot of sense that this problem can be reduced to the Knapsack problem. Time to rewatch your Knapsack video :)
Your videos are just amazing!! Thank you SO much, sir. Your way of explaining hard, complex problems in such a laid-back manner is enthralling to watch!! It's a pleasure subscribing to your channel. Thank you Sir!!!
Thank you so much for this! I have a suggestion for a video maybe; there is barely any info on youtube about bounded knapsack and how to solve it; it took me a good week to understand one of the blogs regarding the topic; could you please make a video on that?
Thank you very much for the video topic suggestion, I do appreciate it! When you say "bounded knapsack", is that different from the typical 0/1 knapsack problem? I ask because that one I covered already here: th-cam.com/video/-kedQt2UmnE/w-d-xo.html
We already can solve this problem in O(S * n). So now we are trying to reduce the number of elements in set. Let K be the number of *unique* elements in set with sum S. Then there is a fact that K
@@stablesort it is useful where you have constraints something like (N < 10^5, S < 2*10^5), if you think about possible sets, you would realise that set must have tons of duplicates
Sounds good, thanks! By the way, I did make a follow up video to this one that you may like, called "Partition K Equal Subset Sum": th-cam.com/video/DB-9JlnbBpM/w-d-xo.html
Thanks for a great explanation! Suggested topic: There are some DP problems where we have two sets of size N1 and N2, and we choose N1 as one dimension and 1
Thanks for suggesting a topic! I do appreciate it and will look into it. I haven't done anything with bitmasks on this channel, so it'll be a good addition =)
Sir , What happened if the weight of the bag is 5^24 then at that condition how would I applied knapsack because knapsack required 0(n*m) auxiliary space I think at that condition I have to go with recursive + backtracking Is this a right choice ?
Yes, that's exactly right: if the capacity of the bag is very large, then creating a giant table becomes a problem. Ultimately, this is an NP-complete problem, so there are limits to what could be computed.
Suppose your numbers are 1, 10. If you divide the sum of them by 2 you get 5.5 even if you round up the result to 6, then 2 partitions each of size 6 can't contain the number 10.
Ahh, the magic of recursion. I struggled with the explenation a bit, but I think i get it now. But like you said, it's a very slow solution so we need to do better. It makes a lot of sense that this problem can be reduced to the Knapsack problem. Time to rewatch your Knapsack video :)
Your videos are just amazing!! Thank you SO much, sir. Your way of explaining hard, complex problems in such a laid-back manner is enthralling to watch!! It's a pleasure subscribing to your channel. Thank you Sir!!!
Happy to help and thanks for the compliment!
U are so good at explaining the concepts properly
Thanks!
Beautiful explanation, I look forward to your future videos
Thanks! More videos are in the making =)
Elegant explanation - thanks for the nice video
Thank you so much for this! I have a suggestion for a video maybe; there is barely any info on youtube about bounded knapsack and how to solve it; it took me a good week to understand one of the blogs regarding the topic; could you please make a video on that?
Thank you very much for the video topic suggestion, I do appreciate it! When you say "bounded knapsack", is that different from the typical 0/1 knapsack problem? I ask because that one I covered already here: th-cam.com/video/-kedQt2UmnE/w-d-xo.html
There is interesting solution that works in O(S*sqrt(S)) where S is sum of the set
Oh cool! Could you please elaborate a little?
We already can solve this problem in O(S * n). So now we are trying to reduce the number of elements in set.
Let K be the number of *unique* elements in set with sum S. Then there is a fact that K
@@stablesort it is useful where you have constraints something like (N < 10^5, S < 2*10^5), if you think about possible sets, you would realise that set must have tons of duplicates
Congratulation 😁😍.please put some more video of dynamic programming. Subset sum, finding the path
Sounds good, thanks! By the way, I did make a follow up video to this one that you may like, called "Partition K Equal Subset Sum":
th-cam.com/video/DB-9JlnbBpM/w-d-xo.html
Very nice and lucid. Thanks.
Thanks for the compliment!
Union Find aka DSU could have been also used in such cases?
Amazing sir !!
Just Amazing
Thanks! Glad to see you enjoyed it =)
Thanks, sir, it helps my understanding a lot :)
Glad to hear it!
Thanks for a great explanation!
Suggested topic: There are some DP problems where we have two sets of size N1 and N2, and we choose N1 as one dimension and 1
Thanks for suggesting a topic! I do appreciate it and will look into it. I haven't done anything with bitmasks on this channel, so it'll be a good addition =)
@@stablesort Thanks! An example of this is: LeetCode 1434. Number of Ways to Wear Different Hats to Each Other
What about if result is negative after subtract value of i from target?
Sir ,
What happened if the weight of the bag is
5^24 then at that condition how would I applied knapsack because knapsack required 0(n*m) auxiliary space I think at that condition I have to go with recursive + backtracking
Is this a right choice ?
Yes, that's exactly right: if the capacity of the bag is very large, then creating a giant table becomes a problem. Ultimately, this is an NP-complete problem, so there are limits to what could be computed.
Велике Вам дякую!
Будь ласка!
Suppose your numbers are 1, 10. If you divide the sum of them by 2 you get 5.5 even if you round up the result to 6, then 2 partitions each of size 6 can't contain the number 10.
the way my professor explained it was very confusing
can we do it in linear time ?
No, not in the general case.
How does 1+10 = 5+7 sir😢
This problem was today's codejam. Very few could solve.
I hope you solved it!
@@stablesort your explanation helped 👍