Greedy Approach is a method of solving problems that involve making a sequence of choices. At each decision point, you pick the option that offers the most immediate benefit. This approach does not always guarantee optimal solution, but does provide a satisfactory solution to the problem with reasonable time frame for certain problems.

Knapsack Problem

It is a classic example of combination / optimization problem that is easy to understand but can be challenging to solve optimally. There will be a set of items given, each with a weight and benefit (value or profit) from which we will have to determine number of items to be included in a collection so that the total weight does not exceed the given limit and the total benefit is maximized.

Steps for Approaching this Problem:

1. Calculate the ratio of benefit to weight for each item.
2. Sort the items by this ratio in decreasing order.
3. Take as much as possible from the item with the highest ratio without exceeding the weight limit.
4. If there is room / space left, move to the next item and repeat until capacity.

0/1 Problem: Each item can be either included or excluded (hence 0 or 1). You cannot break an item, either you pick complete item or don’t pick it.

Fractional Problem:

What is a spanning Tree?

A spanning tree of a graph is a subgraph that includes all the vertices of the original graph and is a tree. It should have no cycles (no path that starts and ends end the same vertex except the trivial path involving no edges). In short spanning tree connects all the vertices together using minimum number of edges (V-1) where V is the number of vertices in the graph.

What is a Minimum Spanning Tree?

It is a spanning tree in which sum of the weights of the edges are as small as possible. This is particularly useful in scenarios where the edges have cost associated with them and the goal is to connect all points in a cost-affective manner.