Help solving this poblem based on dp

general
, ,
1

Anyone please help me in solving this problem based on dp. This is the problem from hackerearth.

2

Ok, so there are 2 dp states, one is the size of the array and the other is X. As these are both maximum 1000 the dp solution will be 10^6.

Now, let’s see how the recursive function works. Let it be f(0,X). Starting from position 0 and remaining number still you can take is X, you can go to three states:

  1. If A[pos]<=X --> take this and be in this position to take more. So, it will be B[pos] + f(pos,X-A[pos])
  2. If A[pos]<=X --> take this and go to the next position. So, B[pos] + f(pos+1, X-A[pos])
  3. You can ignore the number in this position entirely. So, f(pos+1, X)

Hope, it helps! :slight_smile:

3

@sudip_95

Can you please explain in more details what are the overlapping sub problems in this case. Actually I am not able to visualize dp in this problem.

4

This is a basic dp question.

Let’s take an array dp[1001] and dp state is dp[i] contains maximum possible value we can get by taking objects whose sum of weights is less than or equal to i.Now for every weight check for all possible objects and take maximum of all those .Recursive relation be like this

dp[i]=max(dp[i-a[j]]+b[j],dp[i]) if a[j]<=i

Here is my accepted solution and feel free to ask if you have any doubt.

5

I think you should try to build a recursion tree! This is just a simple modification of basic knapsack problem.
Ok, consider this case,

80
2
3 30
6 50

what will be the recursion tree now? (Not building full recursion tree because it’s difficult to draw it here)

              f(0,80)
           /    |      \
      f(0,77)   f(1,77) f(1,80)
    /   |   \ 
 f(0,74) f(1,74) f(1,77)

You see that f(1,77) comes twice. This is a overlapping subproblem. Try to build a recursion tree on your own and you will find many such overlapping subproblems.