Horje Website
Choose maximum weight with given weight and value ratio – Code Tip

Choose maximum weight with given weight and value ratio – A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

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.

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

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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,

 
 
  1. dp(last, diff) = max (dp(last - 1, diff),
  2. dp(last-1, diff + wt[last] - val[last]*K))
  3. dp(last – 1, diff) represents the condition when current
  4. item is not chosen and
  5. dp(last – 1, diff + wt[last] – val[last] * K)) represents
  6. the condition when current item is chosen so difference
  7. 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++

 
 
  1. // C++ program to choose item with maximum
  2. // sum of weight under given constraint
  3. #include
  4. using namespace std;
  5. // memoized recursive method to return maximum
  6. // weight with K as ratio of weight and values
  7. int maxWeightRec(int wt[], int val[], int K,
  8. map& mp,
  9. int last, int diff)
  10. {
  11. // base cases : if no item is remaining
  12. if (last == -1)
  13. {
  14. if (diff == 0)
  15. return 0;
  16. else
  17. return INT_MIN;
  18. }
  19. // first make pair with last chosen item and
  20. // difference between weight and values
  21. pair tmp = make_pair(last, diff);
  22. if (mp.find(tmp) != mp.end())
  23. return mp[tmp];
  24. /* choose maximum value from following two
  25. 1) not selecting the current item and calling
  26. recursively
  27. 2) selection current item, including the weight
  28. and updating the difference before calling
  29. recursively */
  30. mp[tmp] = max(maxWeightRec(wt, val, K, mp, last - 1, diff),
  31. wt[last] + maxWeightRec(wt, val, K, mp,
  32. last - 1, diff + wt[last] - val[last] * K));
  33. return mp[tmp];
  34. }
  35. // method returns maximum sum of weight with K
  36. // as ration of sum of weight and their values
  37. int maxWeight(int wt[], int val[], int K, int N)
  38. {
  39. map mp;
  40. return maxWeightRec(wt, val, K, mp, N - 1, 0);
  41. }
  42. // Driver code to test above methods
  43. int main()
  44. {
  45. int wt[] = {4, 8, 9};
  46. int val[] = {2, 4, 6};
  47. int N = sizeof(wt) / sizeof(int);
  48. int K = 2;
  49. cout
  50. return 0;
  51. }

C++ 2

 
 
  1. // Java program to choose item with maximum
  2. // sum of weight under given constraint
  3. import java.awt.Point;
  4. import java.util.HashMap;
  5. class Test
  6. {
  7. // memoized recursive method to return maximum
  8. // weight with K as ratio of weight and values
  9. static int maxWeightRec(int wt[], int val[], int K,
  10. HashMap hm,
  11. int last, int diff)
  12. {
  13. // base cases : if no item is remaining
  14. if (last == -1)
  15. {
  16. if (diff == 0)
  17. return 0;
  18. else
  19. return Integer.MIN_VALUE;
  20. }
  21. // first make pair with last chosen item and
  22. // difference between weight and values
  23. Point tmp = new Point(last, diff);
  24. if (hm.containsKey(tmp))
  25. return hm.get(tmp);
  26. /* choose maximum value from following two
  27. 1) not selecting the current item and calling
  28. recursively
  29. 2) selection current item, including the weight
  30. and updating the difference before calling
  31. recursively */
  32. hm.put(tmp,Math.max(maxWeightRec(wt, val, K, hm, last - 1, diff),
  33. wt[last] + maxWeightRec(wt, val, K, hm,
  34. last - 1, diff + wt[last] - val[last] * K)));
  35. return hm.get(tmp);
  36. }
  37. // method returns maximum sum of weight with K
  38. // as ration of sum of weight and their values
  39. static int maxWeight(int wt[], int val[], int K, int N)
  40. {
  41. HashMap hm = new HashMap();
  42. return maxWeightRec(wt, val, K, hm, N - 1, 0);
  43. }
  44. // Driver method
  45. public static void main(String args[])
  46. {
  47. int wt[] = {4, 8, 9};
  48. int val[] = {2, 4, 6};
  49. int K = 2;
  50. System.out.println(maxWeight(wt, val, K, wt.length));
  51. }
  52. }
  53. // This code is contributed by Gaurav Miglani

Python3

 
 
  1. # Python3 program to choose item with maximum
  2. # sum of weight under given constraint
  3. INT_MIN = -9999999999
  4. def maxWeightRec(wt, val, K, mp, last, diff):
  5. # memoized recursive method to return maximum
  6. # weight with K as ratio of weight and values
  7. # base cases : if no item is remaining
  8. if last == -1:
  9. if diff == 0:
  10. return 0
  11. else:
  12. return INT_MIN
  13. # first make pair with last chosen item and
  14. # difference between weight and values
  15. tmp = (last, diff)
  16. if tmp in mp:
  17. return mp[tmp]
  18. # choose maximum value from following two
  19. # 1) not selecting the current item and
  20. # calling recursively
  21. # 2) selection current item, including
  22. # the weight and updating the difference
  23. # before calling recursively
  24. mp[tmp] = max(maxWeightRec(wt, val, K, mp,
  25. last - 1, diff), wt[last] +
  26. maxWeightRec(wt, val, K, mp,
  27. last - 1, diff +
  28. wt[last] - val[last] * K))
  29. return mp[tmp]
  30. def maxWeight(wt, val, K, N):
  31. # method returns maximum sum of weight with K
  32. # as ration of sum of weight and their values
  33. return maxWeightRec(wt, val, K, {}, N - 1, 0)
  34. # Driver code
  35. if __name__ == "__main__":
  36. wt = [4, 8, 9]
  37. val = [2, 4, 6]
  38. N = len(wt)
  39. K = 2
  40. print(maxWeight(wt, val, K, N))
  41. # This code is contributed
  42. # by vibhu4agarwal

Javascript

 
 
  1. // JavaScript program to choose item with maximum
  2. // sum of weight under given constraint
  3. const INT_MIN = -9999999999
  4. function maxWeightRec(wt, val, K, mp, last, diff){
  5. // memoized recursive method to return maximum
  6. // weight with K as ratio of weight and values
  7. // base cases : if no item is remaining
  8. if(last == -1){
  9. if(diff == 0)
  10. return 0
  11. else
  12. return INT_MIN
  13. }
  14. // first make pair with last chosen item and
  15. // difference between weight and values
  16. let tmp = [last, diff]
  17. if(mp.has(tmp))
  18. return mp.get(tmp)
  19. // choose maximum value from following two
  20. // 1) not selecting the current item and
  21. // calling recursively
  22. // 2) selection current item, including
  23. // the weight and updating the difference
  24. // before calling recursively
  25. mp.set(tmp, Math.max(maxWeightRec(wt, val, K, mp,
  26. last - 1, diff), wt[last] +
  27. maxWeightRec(wt, val, K, mp,
  28. last - 1, diff +
  29. wt[last] - val[last] * K)))
  30. return mp.get(tmp)
  31. }
  32. function maxWeight(wt, val, K, N){
  33. // method returns maximum sum of weight with K
  34. // as ration of sum of weight and their values
  35. return maxWeightRec(wt, val, K, new Map(), N - 1, 0)
  36. }
  37. // Driver code
  38. let wt = [4, 8, 9]
  39. let val = [2, 4, 6]
  40. let N = wt.length
  41. let K = 2
  42. document.write(maxWeight(wt, val, K, N),"")
  43. // This code is contributed by shinjanpatra

Output:

12

This article is contributed by Utkarsh Trivedi. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to [email protected] See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Source: Geeksforgeeks.org

Published:
November 15, 2022
Author:
admin
Category:
Full Tutorials
Views:
18

This article was posted in Full Tutorials. Bookmark the permalink. Follow comments with the RSS feed for this post.Post a Comment or leave a trackback: Trackback URL.

Leave a Reply

Your email address will not be published. Required fields are marked *

 

Horje © 2011 - 2022