[go: up one dir, main page]
Scribd
Upload
15 views10 pages

Algorithm 6

The document discusses the Greedy Method in algorithm design, which focuses on making the best immediate choice without considering the overall problem. It highlights the Knapsack Problem as a key example, where a thief must choose items to maximize profit within a weight limit. The greedy approach allows for fractional items, emphasizing the importance of immediate benefits in decision-making.

Uploaded by

angelina54320291
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views10 pages

Algorithm 6

The document discusses the Greedy Method in algorithm design, which focuses on making the best immediate choice without considering the overall problem. It highlights the Knapsack Problem as a key example, where a thief must choose items to maximize profit within a weight limit. The greedy approach allows for fractional items, emphasizing the importance of immediate benefits in decision-making.

Uploaded by

angelina54320291
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 10

Algorithm Design & Analysis

CSE 2103
Lecture 6
Chapter 4 : The Greedy Method
2

⚫ Greedy Method : A greedy algorithm is a


mathematical process that looks for simple,
easy-to-implement solutions to complex, multi-step
problems by deciding which next step will provide
the most obvious benefit.
⚫ Such algorithms are called greedy because while the
optimal solution to each smaller instance will
provide an immediate output, the algorithm doesn’t
consider the larger problem as a whole.
⚫ Once a decision has been made, it is never
reconsidered.
The Greedy Method
3

⚫ It picks the best immediate output, but does not


consider the big picture, hence it is considered
greedy.

⚫ For example: Take the path with the largest sum overall. A greedy
algorithm would take the blue path, as a result of shortsightedness, rather than
the orange path, which yields the largest sum.
Example of Greedy Method
4

⚫ Knapsack Problem
⚫ Job Scheduling Problem
⚫ Prim's Minimal Spanning Tree Algorithm
⚫ Minimum-Cost-Spanning Tree
⚫ Kruskal's Minimal Spanning Tree Algorithm
⚫ Single Source Shortest Path
Knapsack Problem
5

⚫ The Greedy algorithm could be understood very well


with a well-known problem referred to as Knapsack
problem.
⚫ Given a set of items, each with a weight and a value,
determine a subset of items to include in a collection
so that the total weight is less than or equal to a
given limit and the total value is as large as possible.
Knapsack Problem
6

⚫ A thief is robbing a store and can carry a maximal weight of


W into his knapsack. There are n items available in the
store and weight of ith item is wi and its profit is pi. What
items should the thief take?
⚫ In this case, items can be broken into smaller pieces, hence
the thief can select fractions of items. According to the
problem statement,
⚪ There are n items in the store
⚪ Weight of ith item wi>0
⚪ Profit for ith item pi>0 and
⚪ Capacity of the Knapsack is W
Knapsack Problem
7

⚫ Remember :
th
⚪ The thief may take only a fraction x of i item
i

⚪ The objective of this algorithm is to

⚪ Subject to constraint

⚫ It is clear that an optimal solution must fill the


knapsack exactly, otherwise we could add a fraction
of one of the remaining items and increase the
overall profit.
Knapsack Problem Example
8
Knapsack Problem Solution
9
10

THANK YOU

You might also like