Skip to content
Gallery
Software Development Mid-Track Exam Refresher
Mid-Track Exam Refresher
Share
Explore
Data Structures and Algorithms

Greedy Approach

Introduction to Greedy Approach

Greedy approach make the best immediate choice at each step, aiming for the best overall solution.
Decisions are made based on current knowledge, without considering future consequences.
Simple and fast, though it may not always lead to the optimal solution.

Example: Paying Exact Amount

Objective: Pay an exact amount with the fewest coins.
Method: Choose the highest value coin less than the remaining amount to be paid.
Illustration: Paying 39 rupees using 20, 10, 5, and two 2-rupee coins, totaling 5 coins.

Characteristics of Greedy Approach

Optimization method seeking the best local choices.
Works well in many practical situations due to simplicity and speed.

Steps to Create a Greedy Solution

Define the objective (e.g., maximize total value, minimize path length).
Set up a process to make the best local choices at each step.

Example: Travelling Salesman Problem

Illustration: Choosing the shortest path at each step may not lead to the best overall path.
Shows the limitation of greedy approach: they may not always yield the globally optimal solution.

Fractional Knapsack Problem

Objective: Maximize the total value of items in a bag with weight constraints.
Items can be divided into fractions to fit the bag.
Greedy approach: Pick items based on value-to-weight ratio.

Steps to Solve Fractional Knapsack Problem

Calculate value-to-weight ratios for each item.
Sort items by their ratios in descending order.
Add items to the bag starting from the highest ratio, taking fractions if needed.

Coding the Fractional Knapsack Problem

Create a class to store item values, weights, and ratios.
Sort the items using a comparator based on the value-to-weight ratio.
Iterate through the sorted items, adding full items or fractions to maximize the total value.

Limitations of Greedy approach

They work well for problems like the fractional knapsack but may fail for the 0/1 knapsack problem, where items cannot be divided.
Example: Adding full items with the highest ratio may not always yield the best result for the 0/1 knapsack problem.
These concepts are important. For more information on Greedy approach, visit this Notion link:
Greedy Approach
⁠
⁠
Want to print your doc?
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.