Recursion  Questions  (Branch & Bound)

The Game Of Weights (codechef )

In this question , there are two cases

 

case1) when barrier[i] < total barrier  ( here we have two options either we can take this or leave this)

case2 ) when barrier[i] > total barrier (here we must have to take this)

Base condition of this recursion , if we reached at last position ,

                                                              and if barrier[i] < total barrier then  

                                                                            return total cost. 

                                                                    else  return total cost+cost[i]

#include<bits/stdc++.h>
using namespace std;

long int  cost[10000];
long int  barrier[10000];
long int  n;

long int  dp[1005][1005];

long int  comp(long int  i,long int  tbarr, long int  tcost)
{
    if(dp[i][tcost])
        return dp[i][tcost];

 if(i==n)
 {
   if(barrier[i]<tbarr)
   {
    return dp[i][tcost]=tcost;
   }
    else
    {
     return dp[i][tcost]=tcost+cost[i];
    }
 }

 if(barrier[i]<=tbarr)
 {
   return dp[i][tcost]=min(comp(i+1,tbarr+barrier[i],tcost+cost[i]), comp(i+1,tbarr,tcost));
 }

 if(barrier[i]>tbarr)
  {
    return dp[i][tcost]=comp(i+1,barrier[i]+tbarr,tcost+cost[i]);
  }
}



int  main()
{

 cin>>n;

 for(long int  i=1;i<=n;i++)
 {
   cin>>cost[i];
   cin>>barrier[i];
 }
cout<<comp(1,0,0)<<endl;;

return 0;
}