Branch_bound.cpp

#include <bits/stdc++.h>
using namespace std;
 /*
    Note:  I haven't tested the code completely but logic is correct and you can manipulate the code to correct minor bugs
    under Creative Common license
    
 */
#define REP(i, a, b) for (int i = a; i <= b; i++)
#define FOR(i, n) for (int i = 0; i < n; i++)
#define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
#define fill(ar, val) memset(ar, val, sizeof(ar))
#define PI 3.1415926535897932385
#define uint64 unsigned long long
#define Int long long
#define int64 long long
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define ff first
#define ss second
#define bit(n) (1<<(n))
#define Last(i) ( (i) & (-i) )
#define sq(x) ((x) * (x))
#define INF INT_MAX
#define mp make_pair

int  n ,  Limit   ;


struct node {  double pwratio ; int weight , profit ;  } ;

bool cmp (  node a,  node b )
 {
     if(  a.pwratio >=  b.pwratio )
     	return true ;
      return false ;
 }


int upper_bound( vector<node>&a,  int mask  )
 {
     int p = 0 ;
     int w = 0 ;

 	 for( int i = n - 1 ; i >= 0 ; i -- )
 	 	 {
             if(  (1<<i) & mask )
              {
                  if(  w + a[i].weight <=  Limit )
                         {  w +=  a[n-i-1].weight ; p+= a[n-i-1].profit ; }
                  else   {  p +=  ( Limit - w )*a[n-i-1].pwratio  ; break ; }


              }

 	 	 }

     return p ;
 }

int knapsack (  vector< node >& a , int weight , int profit  , int  k   , int mask  )
 {

    if(  weight > Limit ) return  0 ;
    if(  k == -1 )return profit ;


    int maxprofit =  knapsack( a , weight + a[n-k-1].weight ,  profit + a[n-k-1].profit  , k - 1 , mask ) ;

    mask &= ~(1 << k);
    int optimum = upper_bound ( a , mask ) ;

     if( optimum >= maxprofit )
        maxprofit =  max(  maxprofit ,  knapsack(  a , weight , profit , k - 1 , mask ) ) ;

     return maxprofit ;


 }


int main (  )
 {
    cin >> n >> Limit ;     // this is for the number of items  and their total capacity
    vector<node>a( n ) ;    // creating an array of struct node which hass three things
    FOR( i , n )
     {
          cin >>  a[i].weight ;
          cin >>  a[i].profit ;
          a[i].pwratio = a[i].profit/(1.0 * a[i].weight) ;   // This calculates the ratio of profit to weight

     }

    sort(  a.begin( ) ,  a.end() ,  cmp ) ; // sorting on the basis of decreasing order of pw ratio




    cout<< knapsack(  a , 0 , 0 , n - 1 , (1<<n) - 1 ) ;

 }