Sudden Tour!

This is a classical 0-1 knapsack problem. Why we are calling it 0-1? Because if we want to take an item we have to take it fully, we can’t take some part of it. If you are interested you can search about ‘fractional knapsack’ on the internet. Let’s see how to solve this problem, if we try to solve it greedily by taking the highest fun value item we will miss cases like this,

1

3 10

9 15

4 8

5 9

Or we want to take items which take minimum space first we will get wrong answer on cases as follows,

1

3 10

1 9

2 10

10 20

So, what we have to do is take all possible combination of the items and see which gives us the maximum output. How can we do that? We have two choices while iterate over the list of items recursively, one is to take the item and other is not to take it, if we take a item we will add the fun value of the item to our current answer, if we don’t take it we will simply move to the next item, for easier understanding see the below pseudo code
cur+=fun[i]+call(i+1,w-cap[i]) [if we take the ith item]
cur+=call(i+1,w) [if we don’t take the ith item]
as we are keep tracking of two things that are which item we are currently trying and what amount of space is remaining so we can understand there will be two states in our dp problem. When we will finished trying every items we will simply return zero from there because we can’t add anything to our answer now.

Time Complexity: As we are trying every items and checking it against the total capacity,time complexity will be O(number of items x total capacity).

Memory Complexity: Usage of the 2D array(to keep track of the two states) gives us the memory complexity of O(number of items x total capacity).