[go: up one dir, main page]
Scribd
Upload
24 views6 pages

DAA Greedy Method,Knacksackprob

Uploaded by

anil shinde
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
24 views6 pages

DAA Greedy Method,Knacksackprob

Uploaded by

anil shinde
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/ 6

Page-1

Chapter-3
Greedy Method

What is Greedy Strategy?


Greedy algorithms are like dynamic programming algorithms that are often used to solve
optimal problems (find best solutions of the problem according to a particular criterion).

Greedy algorithms build a solution part by part, choosing the next part in such a way, that it
gives an immediate benefit. This approach never reconsiders the choices taken previously. This
approach is mainly used to solve optimization problems.

In many problems, it does not produce an optimal solution though it gives an approximate
(near optimal) solution in a reasonable time.

There are two critical components of greedy decisions:

1. Way of greedy selection: Select which solution is best at present and then solve the
subproblem arising from making the last selection. The selection of greedy algorithms
may depend on previous selections. But it cannot depend on any future selection or
depending on the solutions of subproblems.

The algorithm evolves in a way that makes selections in a loop, at the same time
shrinking the given problem to smaller subproblems.

2. Optimal substructure: You perform the optimal substructure for a problem if the
optimal solution of this problem contains optimal solutions to its subproblems.

Components of Greedy Algorithm

Greedy algorithms have the following five components −


 A candidate set − A solution is created from this set.
 A selection function − Used to choose the best candidate to be added to the solution.
 A feasibility function − Used to determine whether a candidate can be used to
contribute to the solution.
 An objective function − Used to assign a value to a solution or a partial solution.
 A solution function − Used to indicate whether a complete solution has been reached.
 Page-2

Areas of Application

Greedy approach is used to solve many problems, such as


 Finding the shortest path between two vertices using Dijkstra’s algorithm.
 Finding the minimal spanning tree in a graph using Prim’s /Kruskal’s algorithm, etc.

Fractional Knapsack
The Greedy algorithm could be understood very well with a well-known problem referred to as
Knapsack problem.
Although the same problem could be solved by employing other algorithmic
approaches(Dynamic programming), Greedy approach solves Fractional Knapsack problem
reasonably in a good time.

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 profit value is as large as possible.
 The knapsack problem is in combinatorial optimization problem.

Applications

 Finding the least wasteful way to cut raw materials


 Cutting stock problems

Problem Scenario
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?
The items should be selected in such a way that the thief will carry those items for which he
will gain maximum profit. Hence, the objective of the thief is to maximize the profit.
Based on the nature of the items, Knapsack problems are categorized as

 Fractional Knapsack(Greedy Method)


 0/1 Knapsack(Dynamic Programming)
 Page-3

Fractional Knapsack

 Items can be broken into smaller pieces


 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
In this Knapsack problem, items can be broken into smaller pieces. So, the thief may take only
a fraction xi of ith item.
0⩽xi⩽1

The ith item contributes the weight xi, wi to the total weight in the knapsack and profit xi,pi to
the total profit.
Hence, the objective of this algorithm is to

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.
Page-4

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W)


for i = 1 to n
do x[i] = 0
weight = 0
for i = 1 to n
if weight + w[i] ≤ W then
x[i] = 1
weight = weight + w[i]
else
x[i] = (W - weight) / w[i]
weight = W
break
return x

Analysis
If the provided items are already sorted into a decreasing order of pi/wi then the
whileloop takes a time in O(n); Therefore, the total time including the sort is
in O(n logn).
Page-5

Solution : Sorting all the items according to pi/wi.


First B is chosen as weight of B is less than the capacity of the knapsack. (Summation of Wi:10)
Next, item A is chosen, as the available capacity of the knapsack is greater than the weight
of A. (Summation of Wi: 10+40=50)
Now, C is chosen as the next item. (Summation of Wi: 10+40+20=70 which is exceeding the
bag capacity)
Therefore whole item cannot be chosen as the remaining capacity of the knapsack is less than
the weight of C. (Remaining capacity is 10)
Hence, fraction of C is chosen. The total weight of the selected items is 10 + 40 + 20 * (10/20)
= 60
Page-6

Now, the capacity of the Knapsack is equal to the selected items. Hence, no more items can be
selected.

And the total profit is 100 + 280 + 120 * (10/20) = 380 + 60 = 440
This is the optimal solution. We cannot gain more profit selecting any different combination of
items.

You might also like