QUESTION :
Given weights and values of N items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
Note: Unlike 0/1 knapsack, you are allowed to break the item.
THOUGHT PROCESS
The logic is simple , sort all the items on basis of 'VALUE PER UNIT' and add whole item if it's weight is less than capacity otherwise
add the portion of that item.
ALGORITHM
- Declare a max priority queue and implement its comparitor based on VALUE PER UNIT
2) Now push every item in pq
3) While (capacity > 0 && pq is not empty) keep poping the top element
3.1) If the top item's weight <= capacity
3.1.1) add it's value in 'total_value' and decrease the capacity by item's weight
3.2) else if item's weight > capacity
3.2.1) increment value accoring to the remaning capacity only and make capacity to zero
==> total_value += (double)top.value / top.weight * capacity;
4) return the total_value
CODE
struct Item
{
int value;
int weight;
};
struct comparitor_
{
bool operator()(Item min, Item max)
{
return (double)max.value / max.weight > (double)min.value / min.weight;
}
};
double fractionalKnapsack(int capacity, Item arr[], int n)
{
priority_queue<Item, vector<Item>, comparitor_> pq;
for (int i = 0; i < n; i++)
{
pq.push(arr[i]);
}
double total_value = 0;
while (capacity && pq.size())
{
auto top = pq.top();
pq.pop();
if (top.weight <= capacity)
{
total_value += top.value;
capacity -= top.weight;
}
else
{
total_value += (double)top.value / top.weight * capacity;
capacity = 0;
}
}
return total_value;
}Comments (10)

