Knapsack Problem Greedy Approach

Learn the Knapsack Problem Greedy Approach, including the Fractional Knapsack algorithm, steps, example, time complexity, and advantages. Maximize profit efficiently with this method.

Knapsack Problem

(Greedy Approach)

Introduction

The Knapsack Problem is a well-known optimization problem. In this problem, we have a bag (knapsack) with a limited capacity, and a set of items, each with a given weight and profit (or value). The objective is to maximize the total profit while staying within the knapsack’s capacity.

Types of the Knapsack Problem

The main types of the Knapsack Problem are:

1. 0/1 Knapsack Problem

• Each item is either taken completely or not taken at all.
• The Greedy method does not always yield the correct solution for this type.

Fractional Knapsack Problem

• Any fraction of an item can be selected.
• The Greedy approach always yields the optimal solution for fractional knapsacks.

Therefore, the Greedy Approach is primarily used for the Fractional Knapsack Problem.

Idea of the Greedy Approach

In the Greedy Approach:

• Calculate the Profit/Weight (P/W) ratio for each item.
• Sort the items in descending order based on this ratio.
• Select the item with the highest P/W ratio first.

Thus, the algorithm makes a locally optimal decision at each step, aiming to achieve the global maximum profit.

Fractional Knapsack Algorithm (Greedy)

Algorithm Steps:

1. Calculate the P/W ratio for each item.
2. Sort the items in descending order according to the P/W ratio.
3. Determine the total capacity, W, of the knapsack.
4. Add items in order:
   • If the item fits completely, take the entire item.
   • Otherwise, take the required fraction of the item.
5. Calculate the total profit.

Algorithm (Pseudo Code)

FractionalKnapsack(W, items)

    Sort items in decreasing order of (profit/weight)

    TotalProfit = 0

    For each item i in items:

        If weight[i] <= W:

            Take full item

            W = W – weight[i]

            TotalProfit += profit[i]

        Else:

            Fraction = W / weight[i]

            TotalProfit += profit[i] * Fraction

            Break

    Return TotalProfit

Example

Given:

Knapsack Capacity = 50

Selection Process:

• Take A fully → Weight = 10, Profit = 60
• Take B fully → Weight = 20, Profit = 100
• Take 2/3 of C → Profit = 80

Total Profit = 60 + 100 + 80 = 240

Time Complexity

• Sorting → O(n log n)
• Selection → O(n)
  Total Time Complexity = O(n log n)

Space Complexity

• Uses minimal additional memory.
• Space Complexity = O(1) (if sorting is done in-place)

Advantages of the Greedy Approach

• Simple and fast to implement.
• Provides the optimal solution for fractional knapsacks.
• Requires less time and memory.
• Easy to understand and implement in practice.

Disadvantages of the Greedy Approach

• Not optimal for the 0/1 knapsack problem.
• The Greedy method does not apply to every problem.
• Local optimal decisions do not always lead to a global optimum.

Conclusion

The Greedy Approach is particularly effective for the Fractional Knapsack Problem. By making decisions based on the P/W ratio, it maximizes total profit efficiently. Although it is not suitable for 0/1 knapsacks, it provides an excellent example for understanding the Greedy Design Technique.

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1