About optimising the space complexity of knapsack 2

#1

I didn’t understand how to optimise the space complexity of this qstn to O(N.V) from O(N^2.V)?pls can you show me the implementation of it.

N=no. of items
V=max val for a item as per constraint.

#2

Hello @Senjuti256 yiou want the optimised code for this question?

#3

Yes because I am not being able to implement the qstn with the reduced space complexity of O(NV).

#4

You can see this code:


if you have any doubt you can ask here:
Happy Learning!!

#5

What is c here? Pls can you tell the logic in brief pls.

#6

@Senjuti256 c here is the capacity as mentioned in the question.

#7

Basically what logic you applied?

#8

Here in this code why haven’t we considered the case when the item will not be included in the knapsack even though it’s weight is less than the capacity of the knapsack?

#9

hello @Senjuti256 the last for loop which we are running till i is less than c in that we are considering that case only.
the idea is that like we have ‘c’ capacity with us and we have to pack maximum values in that range .
so we are calculating for what capacity what is the maximum we can store.
that is why we are running the loop for c times .
and in that loop we have one more loop in which we are making use of last capacities answer and storing the maximum for the present capacity we want to solve for.
if you have any doubt you can ask here:
Happy Learning!!

#10

Pls explain me once again where in this code we are considering the case where we are not taking the current element in the knapsack even though it’s weight is less than the knapsack capacity.

#11

Hello @Senjuti256 in this question we have run one for loop for capacity and in that we are finding the optimised result for every capacity.
if you are not getting that code:
you can see this code:


Happy Learning!!

#12

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.