{"id":1448,"date":"2020-06-11T04:17:47","date_gmt":"2020-06-11T04:17:47","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1448"},"modified":"2022-03-30T11:32:55","modified_gmt":"2022-03-30T11:32:55","slug":"maximum-value","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/maximum-value\/","title":{"rendered":"MAXIMUM VALUE"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Greedy algorithm(fractional knapsack)<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

One day some guests came to Aman’s home. Aman’s mama told him to bring N items from the market and gave him a bag, but the bag can hold a maximum weight of W units. Every item has some weight wi and a value vi. Aman has to put these items in the bag such that the total value is maximized.<\/p>\n

Note: Aman can break items for maximizing the total value of the bag.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example :<\/h4>\n
3 30\n30 8\n40 5\n60 20\n\n121\n\nAman chooses item 2 ,item 1 and 17 g of item 3 (40+30+3*17=121)<\/code><\/pre>\n
OBSERVATION:<\/h3>\n
\n
Since the items can be broken ,the key point in this question is the value \/ unit mass of the item!!<\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
BRUTE FORCE:<\/h4>\n
\n
Try all different subsets that can be formed for the given weight.But that will take exponential time.<\/p>\n<\/blockquote>\n
GREEDY APPROACH:<\/h4>\n
\n
What we\u2019ll do is while the bag is still not full, we will do a greedy choice. We will choose the item number i which has the maximum value of vi over wi, which is the value per unit of weight. And then if this item fits into bag fully, then take off all this item. Otherwise, if there is only few spaces left in the bag, take so much of this item as to fill the bag to the end. And then, in the end, we\u2019ll return the total value of the items that we took and how much did we take off each item.<\/p>\n
    \n
  1. \n
    sort all the items in decreasing order of their value \/ weight ratio.<\/p>\n<\/li>\n
  2. \n
    Start putting the items into the bag beginning from the item with the highest ratio.<\/p>\n<\/li>\n
  3. \n
    Put as many items as you can into the knapsack.<\/p>\n<\/li>\n<\/ol>\n
    Time complexity:<\/strong> The main time taking step is the sorting of all items in decreasing order of their value \/ weight ratio.<\/p>\n<\/blockquote>\n
    SOLUTIONS:<\/h3>\n\t\t\t\t\t\t