Sack of Grains Editorial

Practice Problem Link: Sack of Grains | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a sack which can hold grains of weight w. You have grains of n different varieties, each weighing weight_i kg and having a value of Rs. money_i. What is the maximum worth of grain the sack can be filled with?

Approach

Since it is a fractional knapsack problem, thinking of a brute force approach would be quite difficult. Using a greedy approach is a much better option.

The basic idea to solve this problem is to pick the grain which has the maximum price per unit weight. 

• Sort the array in decreasing order based on the maximum price per unit weight

 (money_i / weight_i).

• Now traverse the sorted array while w is greater than zero and subtract min(weight_i, w) from w and add the effective price to the answer.

Analysis

• Time Complexity: O(n * log(n))
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Grain class definition
class Grain {
public:
   int weight, value;
   Grain(int weight, int value) {
       this->weight = weight;
       this->value = value;
   }
};
*/
bool comp(Grain* A, Grain* B) {
   return ((double)A->value / (double)A->weight) > ((double)B->value / (double)B->weight);
}
double maxSackValue(vector<Grain*> &grains, int w) {
   sort(grains.begin(), grains.end(), comp);
   double price = 0;
   int i = 0;
   while (w > 0 && i < grains.size()) {
       int grainAdded = min (w, grains[i]->weight);
       w -= grainAdded;
       price += (double)grainAdded * ((double)grains[i]->value/(double)grains[i]->weight);
       i++;
   }
   return price;
}

Java

class GrainComparator implements Comparator<Grain> {
   public int compare(Grain A, Grain B) {
       double priceOfA = (double)A.value/(double)A.weight;
       double priceOfB = (double)B.value/(double)B.weight;
       if( priceOfA < priceOfB) {
           return 1;
       } else {
           return - 1;
       }
   }
}
class Solution {
   /* This is the Grain class definition
   class Grain {
       public int weight, value;
       public Grain(int weight, int value) {
           this.weight = weight;
           this.value = value;
       }
   }
   */
   double maxSackValue(Grain[] grains, int w) {
       Arrays.sort(grains, new GrainComparator());
       double price = 0;
       int i = 0;
       while (w > 0 && i < grains.length) {
           int grainAdded = Math.min (w, grains[i].weight);
           w -= grainAdded;
           price += (double)grainAdded * ((double)grains[i].value/(double)grains[i].weight);
           i++;
       }
       return price;
   }
}