Choose maximum weight with given weight and value ratio | Java 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 method
import java . awt . Point ; import java . util . HashMap ; class Test { static int maxWeightRec ( int wt [ ] , int val [ ] , int K , HashMap < Point , Integer > hm , int last , int diff ) { if ( last == - 1 ) { if ( diff == 0 ) return 0 ; else return Integer . MIN_VALUE ; } Point tmp = new Point ( last , diff ) ; if ( hm . containsKey ( tmp ) ) return hm . get ( tmp ) ; hm . put ( tmp , Math . max ( maxWeightRec ( wt , val , K , hm , last - 1 , diff ) , wt [ last ] + maxWeightRec ( wt , val , K , hm , last - 1 , diff + wt [ last ] - val [ last ] * K ) ) ) ; return hm . get ( tmp ) ; } static int maxWeight ( int wt [ ] , int val [ ] , int K , int N ) { HashMap < Point , Integer > hm = new HashMap < > ( ) ; return maxWeightRec ( wt , val , K , hm , N - 1 , 0 ) ; } public static void main ( String args [ ] ) { int wt [ ] = { 4 , 8 , 9 } ; int val [ ] = { 2 , 4 , 6 } ; int K = 2 ; System . out . println ( maxWeight ( wt , val , K , wt . length ) ) ; } }