Unbounded Knapsack using Dynamic Programming Explained with Code

NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we cover the second of the Knapsack Problems i.e. the Unbounded Knapsack problem where we are required to fill a knapsack such that the maximum value is obtained from the weights put into the sack without exceeding its capacity. In this problem,

1. You are given a number n, representing the count of items.
2. You are given n numbers, representing the values of n items.
3. You are given n numbers, representing the weights of n items.
3. You are given a number "cap", which is the capacity of a bag you've.
4. You are required to calculate and print the maximum value that can be created in the bag without overflowing it's capacity.
Note - Each item can be taken any number of times. You are allowed to put the same item again and again.

#dp #dynamicprogramming #knapsack

[ishikamishra]

I have been struggling with recursion and dp for months and out of frustration, I have started cramming the codes until I found you sir. I still can't believe I did the unbounded knapsack myself because of your excellent explanation of 01 knapsack. Thank you so much, sir, you're a savior.

[KalpitSharma]

Yaar ye Teacher mujhe mere college me kyu nahi mila... Khatarnaak Knowledge and teaching skills hai, ek baar me samjh aagya mujhe Knapsack 01 both

[pranjalpatel]

East or west..pepcoding is the the best..i mean literally u actually make us feel how the dp forms...like literally...

[dushyantjakhar]

my life has changes since i started watching the videos form this channel

[Code_Guru]

i think at 18:48 its 1st time i see smile on ur face sir....after Started learning JAVA👏👏👏👏... very nice explained u sir thanks a lot

[ayushgoel]

Sir this new method of teaching is very effective, classroom wali feel aati hai, great idea sirji

[karthiklv]

did this without reference, felt really good, thanks for the well thought out series, cant wait to take the next ones too

[rohansingla]

sir i really like the way of your teaching. i just started watching your videos and you make me easily understand difficult concepts. great sir

[udittyagi]

I LEARNED THIS SAME THING FROM CODING BLOCKS, BUT THEY WAY HE EXPLAINED I THINK I DID A MISTAKE WHILE TAKING A PAID COURSE THANK YOU SO MUCH SIR, I M WAITING FOR YOUR LEVEL 2

[arijitdassharma]

Sir I could solve this question by myself by understanding the previous concepts . Thanks Sir

[rishabh]

Thank you sir, your teaching skills are great 😍😍

[Deepak-lcuu]

Very very very nice content 🔥🔥🔥🔥and the way of teaching 🔥🔥🔥🔥

[tushargupta]

I solved it using the logic in zero-one fractional knapsack, by adding each pair of (cost, weight) multiple times.
for(int i = 0; i < n; ++i){
int cnt = b/w[i] - 1;
while(cnt > 0){
w.push_back(w[i]);
c.push_back(c[i]);
--cnt;
}
}
There should be comments section where we can discuss different approaches.

[sumaiyasafdar]

Your explanation is undoubtedly outstanding. But you used to cut your piece of code and take to the dry run area then explain it. It was a better way of explaining. All the doubts got cleared then because there are so many variable and all. Try to do that sir please like you did it in this vedio. Keep going

[amandixit]

Note : for those who are confused when to use 2D and when to use 1D. i have the confusion today, after going through certain books and vedios, i concluded that we can do the same problem or nearly every problem using only 2D, so why we are using 1D array for quentions involving repetetion.

1. I tried solving the same question using 2D, like in TSS and 0-1 knapsack, we are consedering two choices for every element.

2. to compare how the revenue alter on including or excluding the given weight with corresponding, we are using the row just above the row we are working on( as in if we exclude the element, we have to fill the bag with remaining weights available and for that we have to go for the row just before the very row).

3. Now if we consider for if repetetions are allowed we would check for every element in the row we can dolike --:

(given weight of the ( j) box -- weight of the element we are putting in) for example if the box has weight 4 and we are putting 2, the we will check in the the same row is there any combination exist by which i can fill (4--2) + value of( the weight of the element we are using).

now you can see though we are working in a 2D array, we are still consedering only a perticular row, so as sir suggested its a better way to make 1D array instead of a big 2D array.

[AMANKUMAR-ohzt]

Sir, can there be a system of youtube channel join like thing. Your content is invaluable for lot of students like me. I would like to contribute once i get a job.

[LegitGamer]

sir maine try kiya tha combination se karne ki par bana nahi tha, socha ki yeh tho ban hi nahi sakta combination sey isliye solution video dekhne lag gaya, fir jab aapne samjhaya ki yeh tho combination se bhi ho sakta hai, i went back and tried with combination aur question ban gaya :D, Sir aap lvl 2 mai bhi saath dena 1000 question kya 2000 karlenge hum sab

[khushikapoor]

Sir aise theek sa nhi lg rha, connection sa nhi bann pa rha aapse . Samne dekh kar aap smjhate the acha smjh aata tha.

[samiulkhan]

if we don't use the 2d array and use the combination approch will we get the same answer for this style of problems?
when we are using the 1d method isn't it the permutation approch of coin change permutation?

[loserfruit]

Sir jo recursion backtracking mein pnc mein mehnat ki thi uska yahan fayda ho raha