DP Solution needed!


#1

Has anybody solved this using DP?


#2

Yes, I did but the DP solution (at least top down) is not being accepted due to stack size.

Here it is: https://github.com/meghashyamc/Problems-on-Interview-Bit-Algorithms-and-Data-Structures-/blob/master/dynamicProg/TusharBirthdayBombsDP.java


#3

Classic unbounded knapsack plus back pointer to generate the indexes.

vector<int> bday(int R, vector<int>& p) {
	int n = (int)p.size();
	vector<int> dp(R + 1, -1);
	vector<int> back(R + 1);

	back[0] = 0;
	for (int r = 0; r <= R; r++) {
		for (int i = 0; i < n; i++) {
			if (r >= p[i] && dp[r] < dp[r - p[i]] + 1) {
				dp[r] = dp[r - p[i]] + 1;
				back[r] = i;
			}
		}
	}

	vector<int> ans;
	int r = R;
	while (r >= 0 && (r - p[back[r]]) >= 0) {
		ans.push_back(back[r]);
		r = r - p[back[r]];
	}
	return ans;
}

The lexicographic constraint is solved by using dp[r] < dp[r - p[i]] + 1 (i.e. use < instead of <=), then for a specific resistance you save the index of the kick power that gives you the maximum number of kicks for that resistance (thus, by going backward you generate the steps back). Furthermore, since the kicks have to be smaller than the resistance we have to do this while (r >= 0 && (r - p[back[r]]) >= 0) when you generate the answer.
This was my solution.

The way of thinking: the subproblem is the maximum number of kicks for the resistance r, then for the resistance r+1 you maximize the number of kicks (without exceeding R) by trying all the kicks (choosing the one that maximizes the number - lexicographically: don’t choose one that gives the same number).


#4

https://paste.ofcode.org/vWHbauSQ9bVyY25yMzMFWY
the only problem i faced in creating a dp array was it was giving memory limit. but it worked when i used heap memory


#5

@andrei-pistirica bro,Thank you for your dp solution. Got clarity.


#7

i dont see why you got an AC
you are considering that your answer WILL HAVE TO BE r which is not important…
it might happen that R-2/R-3 had more kicks or lower lexicographic permutation
infact i dont understand how its ever possible to ensure a lower permuataion of indices without actually comparing the answers…
i too solved using unbounded knapsack…got my code accepted…try uncommenting the commented part and you will understand what i am doing

int dp[15000500];
int parent[15000500];


vector<int> Solution::solve(int B, vector<int> &A) {
    
    
    int n = A.size();
    
    
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<=B;i++)
        parent[i] = n+5;
    
    dp[0] = 0;
    
    
    for(int i=0;i<=B;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(A[j]<=i && dp[i-A[j]]!=-1)
            {
                if( (dp[i-A[j]]+1>dp[i]) || (dp[i-A[j]]+1==dp[i] && parent[i]>j) )
                {
                    parent[i] = j;
                    dp[i] = dp[i-A[j]]+1;
                }
            }
        }
    }
    
    vector<int>retval;
    
    int remember = -1;
    
    for(int i=B;i>-1;i--)
    {
        int ans = i;
        vector<int>temp;
        if(dp[ans]!=-1 && dp[ans]>=dp[remember])
        {
            while(ans!=0)
            {
                temp.push_back(parent[ans]);
                ans -= A[parent[ans]];
            }
        }
        // cout<<i<<": ";
        // for(auto it:temp)
        //     cout<<it<<" ";
        // cout<<endl;
        if(temp.size()>retval.size())
        {
            remember = i;
            retval = temp;
        }
        else if(temp.size()==retval.size())
        {

            bool flag = false;
            for(int j=0;j<temp.size();j++)
            {
                if(retval[j]>temp[j])
                {
                    flag = true;
                    break;
                }
                else if(retval[j]<temp[j])
                {
                    break;
                }
            }
            if(flag)
            {
                remember = i;
                retval = temp;
            }
        }
    }
    
    
    
    return retval;
    
}

#8

Excellent soln and thinking !! I was doing it by 2d dp therefore thinking about lexecographic constraint became though for me . Take a bow