Choose maximum weight with given weight and value ratio | C ++ program to choose item with maximum sum of weight under given constraint ; memoized recursive method to return maximum weight with K as ratio of weight and values ; base cases : if no item is remaining ; first make pair with last chosen item and difference between weight and values ; choose maximum value from following two 1 ) not selecting the current item and calling recursively 2 ) selection current item , including the weight and updating the difference before calling recursively ; method returns maximum sum of weight with K as ration of sum of weight and their values ; Driver code to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxWeightRec ( int wt [ ] , int val [ ] , int K , map < pair < int , int > , int > & mp , int last , int diff ) { if ( last == -1 ) { if ( diff == 0 ) return 0 ; else return INT_MIN ; } pair < int , int > tmp = make_pair ( last , diff ) ; if ( mp . find ( tmp ) != mp . end ( ) ) return mp [ tmp ] ; mp [ tmp ] = max ( maxWeightRec ( wt , val , K , mp , last - 1 , diff ) , wt [ last ] + maxWeightRec ( wt , val , K , mp , last - 1 , diff + wt [ last ] - val [ last ] * K ) ) ; return mp [ tmp ] ; } int maxWeight ( int wt [ ] , int val [ ] , int K , int N ) { map < pair < int , int > , int > mp ; return maxWeightRec ( wt , val , K , mp , N - 1 , 0 ) ; } int main ( ) { int wt [ ] = { 4 , 8 , 9 } ; int val [ ] = { 2 , 4 , 6 } ; int N = sizeof ( wt ) / sizeof ( int ) ; int K = 2 ; cout << maxWeight ( wt , val , K , N ) ; return 0 ; }