Given weights and values of n items and a value k. We need to choose a subset of these items in such a way that ratio of the sum of weight and sum of values of chosen items is K and sum of weight is maximum among all possible subset choices.

Input : weight[] = [4, 8, 9] values[] = [2, 4, 6] K = 2 Output : 12 We can choose only first and second item only, because (4 + 8) / (2 + 4) = 2 which is equal to K we can't include third item with weight 9 because then ratio condition won't be satisfied so result will be (4 + 8) = 12

We can solve this problem using dynamic programming. We can make a 2 state dp where dp(i, j) will store maximum possible sum of weights under given conditions when total items are N and required ratio is K.

Now in two states of dp, we will store the last item chosen and the difference between sum of weight and sum of values. We will multiply item values by K so that second state of dp will actually store (sum of weight – K*(sum of values)) for chosen items. Now we can see that our answer will be stored in dp(N-1, 0) because as last item is (N-1)th so all items are being considered and difference between sum of weight and K*(sum of values) is 0 that means sum of weight and sum of values has a ratio K.

After defining above dp state we can write transition among states simply as shown below,

dp(last, diff) = max (dp(last - 1, diff), dp(last-1, diff + wt[last] - val[last]*K)) dp(last – 1, diff) represents the condition when current item is not chosen and dp(last – 1, diff + wt[last] – val[last] * K)) represents the condition when current item is chosen so difference is updated with weight and value of current item.

In below code a top-down approach is used for solving this dynamic programming and for storing dp states a map is used because the difference can be negative also and the 2D array can create problem in that case and special care need to be taken.

## C++

`// C++ program to choose item with maximum ` `// sum of weight under given constraint ` `#include <bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// memoized recursive method to return maximum ` `// weight with K as ratio of weight and values ` `int` `maxWeightRec(` `int` `wt[], ` `int` `val[], ` `int` `K, ` ` ` `map<pair<` `int` `, ` `int` `>, ` `int` `>& mp, ` ` ` `int` `last, ` `int` `diff) ` `{ ` ` ` `// base cases : if no item is remaining ` ` ` `if` `(last == -1) ` ` ` `{ ` ` ` `if` `(diff == 0) ` ` ` `return` `0; ` ` ` `else` ` ` `return` `INT_MIN; ` ` ` `} ` ` ` ` ` `// first make pair with last chosen item and ` ` ` `// difference between weight and values ` ` ` `pair<` `int` `, ` `int` `> tmp = make_pair(last, diff); ` ` ` `if` `(mp.find(tmp) != mp.end()) ` ` ` `return` `mp[tmp]; ` ` ` ` ` `/* 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 ` ` ` `recurively */` ` ` `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]; ` `} ` ` ` `// method returns maximum sum of weight with K ` `// as ration of sum of weight and their values ` `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); ` `} ` ` ` `// Driver code to test above methods ` `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; ` `} ` |

## Java

`// Java program to choose item with maximum ` `// sum of weight under given constraint ` ` ` `import` `java.awt.Point; ` `import` `java.util.HashMap; ` ` ` `class` `Test ` `{ ` ` ` `// memoized recursive method to return maximum ` ` ` `// weight with K as ratio of weight and values ` ` ` `static` `int` `maxWeightRec(` `int` `wt[], ` `int` `val[], ` `int` `K, ` ` ` `HashMap<Point, Integer> hm, ` ` ` `int` `last, ` `int` `diff) ` ` ` `{ ` ` ` `// base cases : if no item is remaining ` ` ` `if` `(last == -` `1` `) ` ` ` `{ ` ` ` `if` `(diff == ` `0` `) ` ` ` `return` `0` `; ` ` ` `else` ` ` `return` `Integer.MIN_VALUE; ` ` ` `} ` ` ` ` ` `// first make pair with last chosen item and ` ` ` `// difference between weight and values ` ` ` `Point tmp = ` `new` `Point(last, diff); ` ` ` `if` `(hm.containsKey(tmp)) ` ` ` `return` `hm.get(tmp); ` ` ` ` ` `/* 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 */` ` ` `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); ` ` ` `} ` ` ` ` ` `// method returns maximum sum of weight with K ` ` ` `// as ration of sum of weight and their values ` ` ` `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` `); ` ` ` `} ` ` ` ` ` `// Driver method ` ` ` `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)); ` ` ` `} ` `} ` `// This code is contributed by Gaurav Miglani ` |

## Python3

`# Python3 program to choose item with maximum ` `# sum of weight under given constraint ` `INT_MIN ` `=` `-` `9999999999` ` ` `def` `maxWeightRec(wt, val, K, mp, last, diff): ` ` ` ` ` `# memoized recursive method to return maximum ` ` ` `# weight with K as ratio of weight and values ` ` ` ` ` `# base cases : if no item is remaining ` ` ` `if` `last ` `=` `=` `-` `1` `: ` ` ` `if` `diff ` `=` `=` `0` `: ` ` ` `return` `0` ` ` `else` `: ` ` ` `return` `INT_MIN ` ` ` ` ` `# first make pair with last chosen item and ` ` ` `# difference between weight and values ` ` ` `tmp ` `=` `(last, diff) ` ` ` `if` `tmp ` `in` `mp: ` ` ` `return` `mp[tmp] ` ` ` ` ` `# 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 ` ` ` ` ` `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] ` ` ` `def` `maxWeight(wt, val, K, N): ` ` ` ` ` `# method returns maximum sum of weight with K ` ` ` `# as ration of sum of weight and their values ` ` ` `return` `maxWeightRec(wt, val, K, {}, N ` `-` `1` `, ` `0` `) ` ` ` `# Driver code ` `if` `__name__ ` `=` `=` `"__main__"` `: ` ` ` `wt ` `=` `[` `4` `, ` `8` `, ` `9` `] ` ` ` `val ` `=` `[` `2` `, ` `4` `, ` `6` `] ` ` ` `N ` `=` `len` `(wt) ` ` ` `K ` `=` `2` ` ` `print` `(maxWeight(wt, val, K, N)) ` ` ` `# This code is contributed ` `# by vibhu4agarwal ` |

**Output:**

12

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments