Knapsack Problem Using Greedy Algorithm
Maissae Azaroual
Nour Riahi Idrissi
Sanae Rabah
Supervised by:
Dr. Rabie Zine
Al Akhawayn University
Operation Research and Optimization
Abstract
The Knapsack problem is a well-known optimization challenge that involves selecting a subset of
items to maximize total value without exceeding a weight limit. This report focuses on identifying
the Knapsack problem within the context of shipping cargo containers. By applying a Greedy
approximation algorithm, we aim to efficiently determine the most valuable combination of
containers to load onto a ship, given its weight capacity. The Greedy algorithm selects containers
based on the highest value-to-weight ratio, providing a practical and efficient solution for
maximizing profit in shipping logistics. This approach, while not always optimal, offers a valuable
heuristic for solving large-scale, real-world problems.
Problem Identification
In logistics, cargo containers are supposed to be loaded on a ship effectively for the maximization
of profit margin with minimization of costs. Every container has a unique weight and profit value.
A vessel -or a ship- also has the maximum limit of weight it may carry. A subset of containers is to
be selected such that a total value is maximum without exceeding the weight limit of the vessel.
This problem is a perfect example of the Knapsack problem.
In this project, we will address the shipping problem using the Knapsack Problem framework and
solve it with a Greedy Approximation Algorithm. The shipping problem involves selecting a subset
of packages, each with a specific weight and value, to maximize the total value of the shipment
without exceeding the weight capacity of the shipping container. By applying the Greedy
Approximation Algorithm, we aim to efficiently determine the most valuable combination of
packages that can be shipped, ensuring an optimal balance between the total weight and value.
Greedy Approximation Algorithm
Greedy Approximation Algorithm is a bit of heuristic applied to formulate a solution for Knapsack
Problem. This kind of method cannot always yield the optimal solution but is quite efficient and
easy to adapt.
Algorithm Steps:
1. First, for each item, calculate a value-to-weight ratio that is: v_i/w_i.
2. Next, the items should be arranged in a list in order of decreasing value-to-weight ratio.
3. Next, the weight and value of the knapsack should be initialized to zero.
4. This point is achieved by going through the sorted list of items.
5. If the item can be included in the knapsack and the overall capacity (W) is not exceeded,
then place it into the knapsack.
6. At the end of each iteration the weight and value of the knapsack are adjusted accordingly.
We stop this process when it becomes impossible to add more items without increasing the overall
capacity.
Conclusion:
The Greedy Approximation Algorithm offers an efficient and uncomplicated approach to
addressing the Knapsack Problem. Although it does not guarantee the optimal solution in every
instance, it proves especially beneficial for extensive datasets where exact algorithms are
impractical due to computational constraints. Recognizing the constraints and potential
applications of this algorithm is essential for effectively resolving practical optimization
challenges.
