Minimum money needed

#1

here how we will make sure that we have taken weights equal to w for minimum money it can also be less then w as in o-n knapsack

#2

@Namanjain123 Try reading subset sum problem using DP and 0-N knapsack again. You will get your answer. If you can’t, then tag me in comments, i’ll tell you.

#3

@abhinandankainth1999
can we do this using 2d dp??? i sloved using 1d

#4

@Namanjain123 Obviously you can. If you can do it in 1D dp you can do that it 2D dp as well. Because in 1D Dp you create a single array for the entire n entities, you can allot a single array to each prefix of entities till n. You can even do 0-1 and 0-N knapsack in 1D.

#5

Can u please tell how to do using 2d how will i make sure that the nth item has infinite supply

#6

for infinite supply you start from w = 1 to w = W. so infinite items are considered. and code it in a similar way as knapsack and add an additional condition to compare in dp[i]'th vector(i.e the current vector as well)

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.