KNAPSACK PROBLEM
USING
GREEDY ALGORITHM
“A Deep Dive into Optimization
Techniques in DAA”
TEAM MEMBERS
Manasvi [RA2311003011192]
Shruti Kulashri [RA2311003011195]
Arya [RA2311003011210]
Ananya Gupta [RA2311003011218]
INTERESTED DOMAIN
Domain: Design and Analysis of Algorithms (DAA)
Focus: Knapsack Problem
What is Knapsack Problem?
Knapsack problem is a classical optimization problem in computer
science and programming. Knapsack problem main objective is to
solve how much the maximum profit can be carried with the knapsack
maximum [Link] item has its own weight and profit.
Importance:
• Used in logistics, finance, scheduling
• Helps in decision-making & resource allocation
QUICK FACT
The name of the problem is derived from the situation in which a
mountain climber should select a number of items to be included in
his knapsack and that he might use during his trip. The difficulty here
is that the climber should select items with more profit but in the
same time should not exceed the capacity of the knapsack.
TECHNIQUE
There are various algorithm that can be used to solve this problem
like brute force, greedy, dynamic programming, and branch and
bound algorithm. But here we will be using Greedy Algorithm
The knapsack problem states that − given a set of items, holding
weights and profit values, one must determine the subset of the
items to be added in a knapsack such that, the total weight of the
items must not exceed the limit of the knapsack and its total profit
value is maximum.
It is one of the most popular problems that take greedy approach
to be solved. It is called as the Fractional Knapsack Problem.
KNAPSACK PROBLEM USING
GREEDY ALGORITHM
The greedy approach works optimally for cases where we can
take fractions of items (hence, Fractional Knapsack).
It does not always work for the 0/1 Knapsack Problem, where
you must take either the whole item or none.
ALGORITHM
1. Calculate value/weight ratio for each item.
2. Sort items in decreasing order of value/weight ratio.
3. Pick items greedily:
If the item fits, take the whole item.
If not, take a fraction of it to fill the remaining space.
Let's understand with an example:-
N = 3, W = 50, values[ ] = {100,60,120}, weight[ ] = {20,10,30}.
The value/weight of item 1 is (100/20) = 5,for item 2 is (60/10) = 6
and for item 3 is (120/30) = 4.
Sorting them in decreasing order of value/weight we have
Initially capacity of bag(W) = 50, value = 0
Item 1 has a weight of 10, we can pick it up.
Current weight = 50 - 10 = 40 ,Current value = 60.00
Item 2 has a weight of 20 , we can pick it up.
Current weight = 40 - 20 = 20 ,Current value = 60.00 + 100.00 =
160.00
Item 3 has a weight of 30 , but current knapsack capacity is [Link]
a fraction of it is chosen.
Current weight = 20 - 20 = 0 ,Final value = 160.00 + (120/30 )*20 =
240.00
TECHNICAL APPLICATION
[Link] Computing & Resource Allocation
💡 Use Case: Efficient allocation of CPU, memory, and bandwidth to
multiple users.
[Link] Systems – Disk Scheduling & Memory Management
💡 Use Case: Optimal file storage and RAM allocation in an OS.
[Link] & Machine Learning – Feature Selection
💡 Use Case: Selecting the most important features from a dataset.
4. Internet & Network Traffic Optimization
💡 Use Case: Maximizing data transfer efficiency over limited bandwidth.
REAL-TIME APPLICATION
[Link] Baggage Optimization – Maximizing cargo value while staying
within weight limits.
[Link] Delivery (Zomato, Swiggy, Uber Eats) – Assigning delivery orders to
riders efficiently.
3. Mobile Data Usage Optimization – Prioritizing important apps when
mobile data is limited.
4. Hospital ICU Bed Allocation – Assigning ICU beds to critical patients
efficiently.
[Link] Relief Supply Distribution – Distributing emergency supplies
effectively after disasters.
6. E-commerce Order Packing (Amazon, Flipkart) – Selecting the most
valuable combination of items to fit in delivery boxes.
TIME COMPLEXITY
Time Complexity: O(N * logN)
Space Complexity: O(N)
Using Master’s Theorem:
Fractional Knapsack, we mainly perform sorting (O(n log n)) followed
by a linear scan (O(n)), which means:
T(n)=T(n/2)+O(n)
The Master Theorem applies to recurrences of the form:
T(n)=aT(n/b)+O(n^d)T(n)
Comparing
a = 1, b=2,d=1,log2(1)=0
Case 3 of the Master Theorem, hence
Time Complexity:O(nlogn)
RECENT RESEARCH
Title: 'Optimization of the Knapsack Problem in Cloud Computing'
Journal: IEEE Transactions on Cloud Computing, 2024
Discusses:
- Resource allocation using Greedy & Dynamic Programming
- Efficiency improvements in cloud storage management
Title:Revolutionizing Multi-Constraint Fractional Knapsack Solutions
Discusses:
This study examines the performance of genetic algorithms (GAs)
compared to the greedy technique for solving the fractional knapsack
problem under multiple constraints
NEWS ARTICLE
THANK YOU