Activity Selection Problem

Proof of Optimality for the Greedy Algorithm in the Activity Selection Problem

We prove that the greedy strategy of always selecting the activity with the earliest finish time yields an optimal solution to the activity selection problem. The proof relies on two key properties:

---

1. Greedy-Choice Property

Claim:
There exists an optimal solution that includes the activity with the earliest finish time.

Proof:
Let $a$ be the activity with the earliest finish time among all activities. Consider an arbitrary optimal solution $A$, with activities sorted by increasing finish times.

• If $a \in A$, the claim trivially holds.
• If $a \notin A$, let the first activity in $A$ be $a_1$. Because $a$ has the earliest finish time, we have:
  $$
  f(a) \le f(a_1)
  $$
  All other activities in $A$ start after $f(a_1)$, and thus must also start after $f(a)$. Therefore, these activities are also compatible with $a$.

We construct a new solution:
$$
A’ = (A \setminus {a_1}) \cup {a}
$$
The set $A’$ has the same size as $A$ and remains mutually compatible. Hence, $A’$ is also optimal and includes $a$.

---

2. Optimal Substructure Property

Claim:
Once the greedy choice is made, solving the remaining subproblem optimally yields an optimal solution for the original problem.

Proof:
After selecting activity $a$, the remaining subproblem is to select a maximum-size subset of mutually compatible activities from the set of activities that start after $a$ finishes. This subproblem has exactly the same structure as the original problem.

Suppose, for contradiction, that the solution to this subproblem is not optimal. Then, there exists a better solution $S’$ for the subproblem. Combining activity $a$ with $S’$ yields a solution better than our previously assumed optimal solution, a contradiction.

Thus, the original optimal solution must contain an optimal solution to the subproblem.

---

Conclusion

Since the activity selection problem satisfies:

1. Greedy-Choice Property: The earliest-finishing activity is always in some optimal solution.
2. Optimal Substructure Property: Optimal solutions can be constructed recursively from optimal subproblem solutions.

The greedy algorithm—selecting activities by earliest finish time—guarantees an optimal solution to the activity selection problem.

---

buying gift problem

---

Proof of Optimality for the Greedy Algorithm in the Buying Gifts Problem

The Buying Gifts Problem asks: Given a budget and a list of candy prices, how can one buy the maximum number of different candies without exceeding the budget?

A natural greedy strategy is to always buy the cheapest available candy first, and repeat until the budget runs out.

To prove this greedy algorithm yields an optimal solution, we establish two properties:

---

1. Greedy-Choice Property

Claim:
The greedy choice—buying the cheapest candy—is always part of some optimal solution.

Proof:
Let the cheapest candy be KitKat, priced at $1. Let$A = {c_1, c_2, \dots, c_t}$be an optimal solution buying$t$candies within budget.

• Case 1: If KitKat is already in$A$, the claim holds.
• Case 2: If KitKat is not in$A$, then because it is the cheapest, we know:$$\text{price}(\text{KitKat}) \le \text{price}(c_i) \quad \forall i$$Replace one candy (say$c_1$) in$A$with KitKat to construct:$$A’ = (A \setminus {c_1}) \cup {\text{KitKat}}$$* Validity: Since KitKat costs no more than$c_1$, the total cost of$A’$is no greater than that of$A$, so it fits within the same budget.
  • Optimality:$A’$contains$t$candies, just like$A$. Thus, it is also an optimal solution.

Hence, the greedy choice (KitKat) can always be included in some optimal solution.

---

2. Optimal Substructure

Claim:
After making a greedy choice, the remaining problem is itself an instance of the same problem, and its optimal solution can be combined with the greedy choice to form the global optimal solution.

Proof:
After purchasing the cheapest candy priced$p$, the problem reduces to:

• A smaller set of remaining candies (excluding the one just bought),
• A reduced budget of$\text{budget} – p$.

Suppose, for contradiction, that the greedy choice is part of the optimal solution, but the remaining candies in the solution are not an optimal solution to the subproblem.

Then there exists a better solution to the subproblem that buys more candies than the one used in the original solution.

By combining the greedy choice with this better subsolution, we obtain a new solution to the original problem that buys more candies than the supposed optimal one—a contradiction.

Therefore, the optimal solution for the whole problem must consist of the greedy choice plus an optimal solution to the subproblem.

---

Conclusion

Since the Buying Gifts Problem satisfies:

1. Greedy-Choice Property — the cheapest candy is always part of some optimal solution, and
2. Optimal Substructure — the remaining problem after a greedy step can be solved optimally and combined with the greedy choice,

the greedy algorithm of repeatedly buying the cheapest available candy guarantees an optimal solution.

This method of proving correctness via Greedy-Choice and Optimal Substructure applies not only to this problem, but to a wide class of greedy algorithms (e.g., Activity Selection, Huffman Coding).

---

Fractional Knapsack Problem

The Fractional Knapsack Problem is one of the most classic examples where a greedy algorithm yields an optimal solution. Unlike the 0/1 Knapsack problem (which requires dynamic programming), the fractional version allows you to take any fraction of an item.

---

✅ Problem Statement

• You are given:
  • A knapsack with capacity W.
  • n items, each with:
    • Value vᵢ
    • Weight wᵢ
• Goal: Fill the knapsack with items (you can take fractions) to maximize total value.

---

✅ Greedy Strategy

• Sort items by value-to-weight ratio (density): $\frac{vᵢ}{wᵢ}$, in descending order.
• Then, greedily take as much of the item with the highest ratio as possible, until the knapsack is full.

---

✅ Claim

The greedy algorithm always yields an optimal solution to the fractional knapsack problem.

---

✅ Proof of Optimality

We prove the correctness of the greedy approach using the Greedy-Choice Property and Optimal Substructure.

---

🔸 1. Greedy-Choice Property

If there is an optimal solution, then there exists an optimal solution that includes the greedy choice (i.e., the item with highest value-to-weight ratio).

Let’s suppose item i has the highest ratio $\frac{vᵢ}{wᵢ}$.

Now suppose, for contradiction, that in some optimal solution, we do not take item i, but take other items with lower value-to-weight ratios.

Then, by removing a small amount of those less efficient items (with total weight = ε) and replacing it with ε weight of item i, the total weight stays the same, but the total value increases, since:
$$
\frac{vᵢ}{wᵢ} > \frac{v_j}{w_j} \quad \Rightarrow \quad \text{Value gained from } i > \text{Value lost from } j
$$
So the original solution wasn’t optimal — contradiction.

Thus, there must exist an optimal solution that includes the greedy choice.

---

🔸 2. Optimal Substructure

After choosing the best item (or fraction), we reduce the problem to a smaller instance:

• New capacity $W’ = W – wᵢ$
• Remaining items (excluding the one just taken, or reducing its weight if partially taken)

Since this subproblem is of the same structure, the same greedy approach works on the reduced problem.

Hence, we can recursively apply the greedy choice and build an optimal solution.

---

✅ Conclusion

Since:

1. Greedy-choice property holds (the best ratio item must be in some optimal solution)
2. Optimal substructure exists (smaller subproblems are also optimal),

➡️ The greedy algorithm is guaranteed to produce an optimal solution for the Fractional Knapsack Problem.