Scribd
Upload
37 views2 pages

What Is Not Greedy Algorithm

The document explains the differences between greedy and non-greedy algorithms, highlighting that non-greedy algorithms consider broader possibilities for achieving a global optimal solution. It uses the 0/1 Knapsack Problem as an example, demonstrating how a greedy approach can fail to find the best solution, while a non-greedy approach like Dynamic Programming can yield a better result. The optimal solution in the example is achieved by selecting items B and C, resulting in a total value of $220.

Uploaded by

Jason Hasonh
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
37 views2 pages

What Is Not Greedy Algorithm

The document explains the differences between greedy and non-greedy algorithms, highlighting that non-greedy algorithms consider broader possibilities for achieving a global optimal solution. It uses the 0/1 Knapsack Problem as an example, demonstrating how a greedy approach can fail to find the best solution, while a non-greedy approach like Dynamic Programming can yield a better result. The optimal solution in the example is achieved by selecting items B and C, resulting in a total value of $220.

Uploaded by

Jason Hasonh
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/ 2

Name: Paidomama, Jason M.

Year/Course/Section: 2-BSInfoSys-A

It is more helpful to understand "non-greedy" algorithms as algorithms that do not rely on the
greedy approach to find a solution.

Understanding the Non-Greedy Approach


A greedy algorithm makes the locally optimal choice at each step, hoping that this sequence of
local best choices will lead to the globally optimal solution. It is "short-sighted" and never
reconsiders its past decisions.
A non-greedy algorithm, in contrast, is an algorithm that does not follow this strict locally
optimal, non-revisiting strategy. They often consider a broader set of possibilities or the
long-term consequences of a choice, aiming for the absolute best (global) solution.
The key differences are:
●​ Perspective: Non-greedy algorithms consider the global optimal solution; greedy ones
focus on the local best choice.
●​ Decision-making: Non-greedy algorithms often explore multiple paths or use information
about the overall problem structure (like in Dynamic Programming or searching
algorithms) before committing to a choice.

Example: The 0/1 Knapsack Problem


The 0/1 Knapsack Problem is a classic example where a greedy approach fails to find the
optimal solution, thus requiring a non-greedy approach like Dynamic Programming.
The Problem: You have a knapsack with a maximum weight capacity, W. You have a set of
items, each with a specific weight w and value v. You must decide, for each item, whether to put
it in the knapsack (1) or not (0), to maximize the total value without exceeding the capacity W.
Item Weight (w) Value (v) Value-to-Weight Ratio
(v_i/w_i)
A 10 kg $60 6
B 20 kg $100 5
C 30 kg $120 4
Let the capacity W = 50 kg.

1. The Greedy Approach (Fails)

A common greedy strategy is to always pick the item with the highest Value-to-Weight Ratio
first, as this seems like the "best local choice."
1.​ Choose Item A (Ratio 6):
○​ Knapsack: {A}
○​ Total Weight: 10 kg
○​ Total Value: $60
○​ Remaining Capacity: 50 - 10 = 40 kg
2.​ Choose Item B (Ratio 5):
○​ Knapsack: {A, B}
○​ Total Weight: 10 + 20 = 30 kg
○​ Total Value: $60 + $100 = $160
○​ Remaining Capacity: 50 - 30 = 20 kg
3.​ Attempt to Choose Item C (Ratio 4):
○​ Item C weighs 30 kg, which is greater than the remaining capacity of 20 kg. It
cannot be chosen.
4.​ Greedy Solution: $160 (Items A and B).

2. The Non-Greedy Approach (Optimal: Dynamic Programming)

A non-greedy approach, like Dynamic Programming, systematically considers all possible


optimal substructures to guarantee the global best solution. In this case, we'll see that a
combination of items that doesn't use the "best" local choice (Item A) yields a better result.
1.​ Consider Items B and C:
○​ Total Weight: 20 + 30 = 50 kg
○​ Total Value: $100 + $120 = {$220}
○​ This combination is feasible (50 kg le 50 kg) and has a higher value.
Optimal Solution (Non-Greedy): $220 (Items B and C).
The greedy algorithm failed because its "locally optimal" choice (Item A) prevented the inclusion
of two other items (B and C) that together formed the globally optimal solution. The non-greedy
algorithm overcomes this by ensuring that all relevant combinations (or subproblems) are
considered.

You might also like