FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

Fractional Knapsack Problem



Fractional Knapsack Problem

The Fractional Knapsack Problem is one of the most important applications of the Greedy Method. In this problem, a knapsack has a fixed carrying capacity, and several items with different weights and profits are available. The objective is to maximize the total profit without exceeding the capacity of the knapsack.

Unlike the 0/1 Knapsack Problem, the Fractional Knapsack allows an item to be divided into smaller parts. Therefore, if the complete item cannot be placed inside the knapsack, a fraction of that item may be selected. This flexibility makes the Greedy approach produce the optimal solution.

Problem Statement

Given a set of items, each having a weight and profit, and a knapsack with limited capacity, determine the maximum profit that can be obtained by selecting complete or fractional items.

Real-Life Example

Suppose a truck can carry only 50 kg of goods. Different products have different weights and profits. If the truck becomes full before taking an entire item, a portion of that item may still be loaded to maximize the total profit.

This is the basic idea behind the Fractional Knapsack Problem.

Input Data

Item Weight (kg) Profit (₹) Profit / Weight
A 10 60 6
B 20 100 5
C 30 120 4

Working Principle

The Greedy strategy selects items according to the highest Profit / Weight Ratio. Items having greater value per unit weight are selected first to maximize the total profit.

Illustration


Knapsack Capacity = 50 kg

Item A  → Take Complete

Item B  → Take Complete

Remaining Capacity = 20 kg

Item C  → Take only 20/30

Maximum Profit Obtained

Figure 1 : Fractional Knapsack using Greedy Method

Step-by-Step Example

Step Selected Item Remaining Capacity Total Profit
1 A (10 kg) 40 kg 60
2 B (20 kg) 20 kg 160
3 2/3 of Item C 0 kg 240

Fractional Knapsack Algorithm

FractionalKnapsack(Items, Capacity) Step 1 : Calculate Profit / Weight ratio for each item. Step 2 : Sort all items in descending order of Profit / Weight ratio. Step 3 : Select the item having the highest ratio. Step 4 : If the complete item fits, include it. Step 5 : Otherwise, include only the required fraction. Step 6 : Repeat until the knapsack becomes full.

Complexity Analysis

Case Complexity Explanation
Sorting Items O(n log n) Items are sorted according to their Profit / Weight ratio.
Item Selection O(n) Each item is visited only once.
Total Time Complexity O(n log n) Sorting dominates the execution time.
Space Complexity O(1) Only a few variables are required apart from the input array.

Advantages

  • Provides the optimal solution for the Fractional Knapsack Problem.
  • Simple and easy to implement.
  • Efficient due to Greedy strategy.
  • Suitable for maximizing profit with limited resources.
  • Runs efficiently for large datasets.

Limitations

  • Applicable only when items can be divided into fractions.
  • Cannot solve the 0/1 Knapsack Problem optimally.
  • Requires sorting of items before selection.
  • Depends on the Profit / Weight ratio.

Applications

Application Description
Cargo Loading Maximizing profit while loading goods into trucks or ships.
Investment Planning Allocating funds among multiple investment options.
Cloud Resource Allocation Efficient allocation of computing resources.
Bandwidth Allocation Distributing network bandwidth efficiently.
Production Planning Selecting products to maximize revenue.

Fractional Knapsack vs 0/1 Knapsack

Fractional Knapsack 0/1 Knapsack
Items can be divided. Items cannot be divided.
Greedy Algorithm is used. Dynamic Programming is generally used.
Produces the optimal solution using Greedy. Greedy does not always produce the optimal solution.
Based on Profit / Weight ratio. Based on overall optimization.

Important Points

  • Items are selected according to the highest Profit / Weight ratio.
  • Fractional parts of items are allowed.
  • Greedy Method always gives the optimal solution for this problem.
  • Overall Time Complexity is O(n log n).
  • It differs from the 0/1 Knapsack Problem where items cannot be divided.

Exam Tip

In AKTU examinations, students are commonly asked to distinguish between the Fractional Knapsack Problem and the 0/1 Knapsack Problem. Remember that the Fractional Knapsack allows items to be divided and is solved optimally using the Greedy Method, whereas the 0/1 Knapsack does not allow fractional selection and is typically solved using Dynamic Programming.







Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com