Not able to do top down dp

#1

i don’t know where i failed to implement top down dp.
here’s my java code link:

#2

Hi Umapati
I will check it for the errors

#3

please check this is the link–https://ide.codingblocks.com/s/257492

#4 
int solve(int x)
{
    if (x==0)
        return 1;
    if (dp[x]!=-1)
        return dp[x];
    return (dp[x] = x * solve(x-1));
}

Thsi is top down DP(memoization)

int f(List<List<Integer>> group,int i,int j,int x){
		if(x<=0)
		  return 0;
		if(i>=group.size() || j>=group.get(i).size())
		    return 0;

		int result=0;
		if(group.get(i).get(j)>x)
		    result= f(group,i,j+1,x);
		for(int k=j;k<group.get(i).size();k++){
			 int temp1=0;
			 if(group.get(i).get(k)<=x)
		        temp1=group.get(i).get(k)+f(group,i+1,0,x-group.get(i).get(k));
		     int temp2=f(group,i,k+1,x);
		     result=Math.max(temp1,temp2);
		}
		return result;
	}

This is your code
The difference between you method and the top down DP is that you have not memoised your solution. What you are doing is just recursion.
The way to make your solution into a top down DP solution is to create an auxiliary storage space that checks whether f(group,i,j,x) is already pre-computed or not.

#5
#6

bhai mere recursion kaam nhi kar rha , memoization to baad me bhi ho jayega but ek baar recursion to smajh jaa, ek baar check karlo memoization ke saath code bhej dia haiu

#7

Thik hai dekhta Hu
Merko wahi tha ki Aapne Bola top down DP Nahi lag rahi thi to meine bataya ki memoization Nahi Kara hai
Baaki recursion check karta abhi poora code bhej Diya na Apne?

#8
1 Like
#9

i will be very thankful for your help

1 Like
#10 
for j from 1 to x:
	dp[1][j]=-1
	for weight in vector(1):
		if weight<=j:
			dp[1][j]=max(dp[1][j],weight)

for i from 2 to m:
	for j from 1 to x:
		dp[i][j]=-1
		if i>x:
			break
		for weight in vector(m):
			if j>weight && dp[i-1][j-weight]>0:
				dp[i][j]=max(dp[i][j],dp[i-1][j-weight]+weight)
#11

This is the pseudo code of colorful knapsack, however it is bottom up and not top down. We just need to convert it to top down which is fairly easy.

#12 
int knapsack(int index, int size, int weights[],int values[]){
    int take,dontTake;

    take = dontTake = 0;

    if (matrix[index][size]!=0)
        return matrix[index][size];

    if (index==0){
        if (weights[0]<=size){
            picks[index][size]=1;
            matrix[index][size] = values[0];
            return values[0];
        }
        else{
            picks[index][size]=-1;
            matrix[index][size] = 0;
            return 0;
        }
    }

    if (weights[index]<=size)
        take = values[index] + knapsack(index-1, size-weights[index], weights, values);

    dontTake = knapsack(index-1, size, weights, values);

    matrix[index][size] = max (take, dontTake);

    if (take>dontTake)
        picks[index][size]=1;
    else
        picks[index][size]=-1;

    return matrix[index][size];

}
#13

thanks ,i will try this

#14

This is the pseudo code of 0/1 knapsack but in top down dp mode
As we know, colorful knapsack is an extension of 0/1 knapsack where we have to group the stones color wise.

#15

So this is our hint> See if you can convert colorful knapsack bottom up dp into top down dp using the 0/1 knapsack code. If not, let me know

#16

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.