Greedy Algorithm-Fractional Knapsack Problem
What is a Greedy Algorithm?
Suppose we have an optimization problem.
An optimization problem asks us to find the best possible solution according to some objective.
For example:
- maximum profit
- minimum cost
- minimum distance
- maximum number of activities
- maximum value that can be carried
A greedy algorithm solves such a problem by making a sequence of choices.
At every step:
Choose the option that looks best right now.
It does not go back and change the decision later.
This is called the greedy choice.
The important point is that greedy algorithms do not always give an optimal solution. They work only for problems where the greedy-choice property can be established.
2. Simple Real-Life Example
Imagine that you have ₹100 and want to buy the maximum amount of food.
Suppose you have several options.
A simple greedy approach might be:
"At every step, buy the item that gives me the maximum benefit for my money."
This sounds reasonable, but we must be careful.
A locally best choice does not necessarily guarantee the globally best solution.
Therefore, for a greedy algorithm to be correct, we need to establish that the greedy choice is safe.
3. Basic Structure of a Greedy Algorithm
A greedy algorithm generally follows this pattern:
Start with an empty solution while the solution is not complete: select the best available choice if the choice is feasible: add it to the solution return the solution
The important part is:
select the best available choice
This is the greedy step.
4. Greedy Choice Property
The most important concept is the greedy-choice property.
It means:
We can obtain a globally optimal solution by making a locally optimal choice at each step.
In other words:
Best choice now ↓ Remaining problem ↓ Best choice now ↓ Remaining problem ↓ ... ↓ Optimal solution
Unlike dynamic programming, a greedy algorithm makes its choice before solving the remaining subproblem.
5. Greedy Algorithm vs Dynamic Programming
This distinction is very important for undergraduate students.
| Greedy | Dynamic Programming |
|---|---|
| Makes the best choice at the current step | Considers different choices |
| Choice is made immediately | Choices depend on subproblem solutions |
| Usually proceeds top-down | Usually proceeds bottom-up |
| Does not reconsider a choice | Can compare alternative solutions |
| Usually simpler | Usually more computational work |
| Does not always produce optimal solutions | Designed to obtain optimal solutions when applicable |
For example, the fractional knapsack problem can be solved greedily.
However, the 0-1 knapsack problem cannot generally be solved by the same greedy strategy.
6. What is Greedy Control Abstraction?
A control abstraction describes the general structure of an algorithm without going into the details of a particular problem.
For a greedy algorithm, we can think of the control abstraction as:
GREEDY(A) S = empty solution while solution is not complete: choose the best available candidate if candidate is feasible: add candidate to S return S
Here:
- A = set of available candidates
- S = solution being constructed
- choose = problem-specific greedy rule
- feasible = whether the candidate can be included
- complete = whether we have obtained the required solution
The control structure is common, but the actual choice depends on the problem.
7. Important Components of Greedy Control Abstraction
We can break it into four simple components.
1. Candidate set
These are the choices available to us.
Example:
Items = {Item 1, Item 2, Item 3, Item 4}
2. Selection rule
How do we decide which candidate is best?
For example:
Choose the item having the highest value per kilogram.
This is the greedy rule.
3. Feasibility test
After selecting a candidate, we check:
Can I include this candidate without violating the problem constraints?
For example:
Does the item fit inside the remaining capacity?
4. Solution
If the candidate is feasible, we add it to our solution.
Eventually, we obtain the final solution.
8. Fractional Knapsack Problem
Now let us use the fractional knapsack problem as an example of a successful greedy algorithm.
Suppose a thief has a knapsack that can carry at most W kilograms.
There are n items.
Each item has:
- a weight
- a value
The objective is:
Maximize the total value placed in the knapsack.
The important difference is that in the fractional version, we can take a fraction of an item.
For example, we can take:
- 1 kg of an item
- 5 kg of an item
- 50% of an item
- 75% of an item
This makes the problem suitable for a greedy strategy.
9. Example
Suppose the knapsack capacity is:
W = 50 kg
We have three items:
| Item | Weight | Value |
|---|---|---|
| Item 1 | 10 kg | ₹60 |
| Item 2 | 20 kg | ₹100 |
| Item 3 | 30 kg | ₹120 |
Our objective is:
Put items into the knapsack so that the total value is maximum.
10. Why Weight Alone Is Not Enough
Suppose we look only at weight.
Item 1 weighs 10 kg.
Item 2 weighs 20 kg.
Item 3 weighs 30 kg.
But weight alone doesn't tell us which item is more profitable.
We should ask:
How much value do we obtain for every kilogram?
So we calculate:
Value per kilogram = Value / Weight
11. Calculate Value per Kilogram
Item 1
Value = ₹60
Weight = 10 kg
Therefore:
60 / 10 = ₹6 per kg
Item 2
Value = ₹100
Weight = 20 kg
Therefore:
100 / 20 = ₹5 per kg
Item 3
Value = ₹120
Weight = 30 kg
Therefore:
120 / 30 = ₹4 per kg
So:
| Item | Weight | Value | Value/kg |
|---|---|---|---|
| Item 1 | 10 | ₹60 | ₹6 |
| Item 2 | 20 | ₹100 | ₹5 |
| Item 3 | 30 | ₹120 | ₹4 |
12. The Greedy Choice
Which item should we take first?
We choose:
Item 1
because it has the highest value per kilogram.
This is the greedy choice.
Then we choose:
Item 2
because it has the next highest value per kilogram.
Finally, we use Item 3 if there is still capacity available.
Thus the greedy rule is:
Always take as much as possible of the item having the highest value per unit weight.
This is exactly the greedy strategy described in CLRS.
13. Solving the Example Step by Step
Knapsack capacity:
50 kg
Step 1: Take Item 1
Item 1:
10 kg → ₹60
Remaining capacity:
50 − 10 = 40 kg
Current value:
₹60
Step 2: Take Item 2
Item 2 weighs 20 kg.
We can take the entire item.
Value:
₹100
Remaining capacity:
40 − 20 = 20 kg
Current value:
₹60 + ₹100 = ₹160
Step 3: Item 3
Item 3 weighs 30 kg.
But only 20 kg capacity remains.
Because this is the fractional knapsack problem, we don't have to reject Item 3.
We can take 20 kg out of the 30 kg.
The value per kilogram of Item 3 is:
₹4/kg
Therefore, value of 20 kg is:
20 × 4 = ₹80
14. Final Solution
| Item | Amount Taken | Value |
|---|---|---|
| Item 1 | 10 kg | ₹60 |
| Item 2 | 20 kg | ₹100 |
| Item 3 | 20 kg | ₹80 |
| Total | 50 kg | ₹240 |
Therefore:
Maximum value = ₹240
The knapsack is completely filled.
15. Why Does the Greedy Strategy Work Here?
This is the most important conceptual question.
Suppose we have 1 kg of free space.
Which item should we use for that 1 kg?
Obviously, we should use the item that gives the highest value per kilogram.
If Item 1 gives:
₹6/kg
and Item 3 gives:
₹4/kg
using 1 kg of Item 3 instead of Item 1 would lose:
₹2
of potential value.
Therefore, taking the highest-value-per-kilogram item first is always safe in the fractional case.
The ability to take fractions is the key reason the greedy strategy works.
16. Greedy Control Abstraction for Fractional Knapsack
We can now apply our general greedy control abstraction.
FRACTIONAL-KNAPSACK Input: n items weight of each item value of each item knapsack capacity W Step 1: Calculate value/weight for every item. Step 2: Sort items in decreasing order of value/weight. Step 3: Start with an empty knapsack. Step 4: Consider items one by one. Step 5: If the complete item fits: take the complete item. Otherwise: take only the fraction that fits. Step 6: Stop when the knapsack is full. Output: Maximum total value.
17. Pseudocode
A simple version suitable for undergraduate students is:
FRACTIONAL-KNAPSACK(items, W) calculate value/weight for every item sort items in decreasing order of value/weight totalValue = 0 for each item: if item.weight <= W: take the entire item W = W - item.weight totalValue = totalValue + item.value else: take W units of the item totalValue = totalValue + W × item.value/item.weight W = 0 break return totalValue
18. Complexity Analysis
Suppose there are n items.
Step 1: Calculate value/weight
We calculate the ratio for every item.
Time:
O(n)
Step 2: Sort the items
We sort according to value/weight.
Time:
O(n log n)
Step 3: Traverse the items
We examine every item at most once.
Time:
O(n)
Therefore:
Total time = O(n) + O(n log n) + O(n)
Hence:
Total time = O(n log n)
Sorting the items by value per pound gives an O(n log n) greedy algorithm.
If the items are already sorted by value/weight, the selection phase itself takes:
O(n)
19. Why Doesn't This Work for 0-1 Knapsack?
This is a very important point.
In 0-1 knapsack, we cannot take a fraction.
We must either:
Take the entire item OR Do not take the item
Consider the same example:
| Item | Weight | Value | Value/kg |
|---|---|---|---|
| 1 | 10 | ₹60 | ₹6 |
| 2 | 20 | ₹100 | ₹5 |
| 3 | 30 | ₹120 | ₹4 |
Capacity = 50 kg
The greedy method first chooses Item 1 because it has the highest value/kg.
Remaining capacity:
50 − 10 = 40 kg
We can then take Item 2.
Total:
10 + 20 = 30 kg
Value:
₹60 + ₹100 = ₹160
We cannot take Item 3 because it weighs 30 kg and the remaining capacity is 20 kg.
So greedy gives:
₹160
But the optimal solution is:
Item 2 + Item 3
Weight:
20 + 30 = 50 kg
Value:
₹100 + ₹120 = ₹220
Therefore:
Greedy solution = ₹160
Optimal solution = ₹220
So the same greedy rule fails for 0-1 knapsack. This example is used to show precisely why fractional and 0-1 knapsack behave differently.
20. The Key Difference
The difference can be summarized very simply:
Fractional Knapsack
Can take fractions ↓ Can always use remaining capacity ↓ Highest value/kg is safe ↓ Greedy works
0-1 Knapsack
Cannot take fractions ↓ An item may leave unusable space ↓ Highest value/kg may not be the best choice ↓ Greedy does not always work
21. What Students Should Remember
For a greedy algorithm, remember these four ideas:
1. Greedy choice
Choose what looks best right now.
2. Feasibility
Make sure the choice does not violate the constraints.
3. Greedy-choice property
There must be a proof that making the greedy choice can still lead to an optimal solution.
4. Optimal substructure
After making the greedy choice, the remaining problem should have the appropriate optimal-substructure property. CLRS identifies greedy-choice property and optimal substructure as the two key ingredients for determining whether a greedy approach will solve an optimization problem.
Comments
Post a Comment