Fractional Knapsack

Hello, This is my first post and I am going to talk about Factional Knapsack problem in DSA. This is often asked in interviews or university exams.

What is a Knapsack?

Knapsack is a bag you carry over your shoulders. Best example can be your schoolbag.

What is Greedy approach in programming?

• During your programming journey you have heard of the greedy approach to finding solutions at least once. A greedy approach is the exercise of picking the best/optimum solution in the given time without considering future consequences.
• The knapsack problem is optimally solved by the greedy approach though it is entirely possible to have other approaches that lead to the solution space, just not optimal in terms of Time and Space complexity. Greedy technique is a simple intuitive technique created by Dijsktra for calculating a minimum spanning tree. It was made for graph optimization but can be used in a lot of different ways.

Fractional Knapsack paramters

• This problem has 4 given parameters:

  1. Profit/Value
  2. Weight
  3. Number of items
  4. Carry Capacity of the knapsack

• Let these parameters be {value= p, weight= w, item_amt= n, capacity_of_bag= c}

Objective of the problem

Fractional Knapsack differs from 0/1 Knapsack such that we are allowed to put parts of an item into the bag whereas in 0/1 knapsack we either stuff it in or we don't. Therefore we must use floats or similar fractional data type for our operations. The goal is to maximize the total value of the items in the knapsack, given the weight capacity constraint. You can take fractions of items to achieve the optimal value.

Algorithm

• Sort all items by their value-to-weight ratio in decreasing order. This ratio is calculated as p[i] / w[i] where i is the item from index [0 to n].
• Iterate through the sorted items and pick as much of each item as possible. If an item’s weight exceeds the remaining capacity, take only the fraction of that item that fits.
• Continue this process until the knapsack is full, ensuring you maximize the total value."

Let’s take three items:

Item 1: Value = 60, Weight = 10
Item 2: Value = 100, Weight = 20
Item 3: Value = 120, Weight = 30
The capacity of the knapsack is 50.

First, calculate the value-to-weight ratio for each item:

Item 1: 60/10 = 6
Item 2: 100/20 = 5
Item 3: 120/30 = 4
Now sort the items by their value-to-weight ratio:

Item 1 (6)
Item 2 (5)
Item 3 (4)

The greedy algorithm picks the highest ratio first, so we pick Item 1 entirely (10 weight), then Item 2 (20 weight), and finally, we take half of Item 3 (15 weight).

The total value of the items in the knapsack is: 60 (from Item 1) + 100 (from Item 2) + 60 (half of Item 3's value) = 220

The formula to calculate the fractional value is:

fractional value = (remaining capacity / weight of the item) × value of the item

• Note that in some problems we might be allowed to reselect an item more than once.

Time Complexity

Since sorting takes O(n log n) time (where n is the number of items), the overall time complexity of the algorithm is O(n log n).