In the Fractional Knapsack Problem with n items, item i has value $v_{i}$ and weight $w_{i}$. What is the greedy choice strategy that guarantees an optimal solution?
Fractional knapsack exhibits optimal substructure and greedy choice property when items are selected in decreasing order of value-to-weight ratio $v_{i}$ / $w_{i}$.
What is the time complexity of solving the Fractional Knapsack problem for n items when item ratios are not pre-sorted?
Sorting n items by $v_{i}$/$w_{i}$ ratio takes O(n log n) time. The subsequent greedy selection takes O(n) time, making total time O(n log n). Note: Linear time O(n) is achievable using Median-of-Medians select.
Why does the Greedy choice strategy fail for the 0/1 Knapsack Problem?
In 0/1 Knapsack, taking an item with high $v_{i}$/$w_{i}$ ratio may fill capacity such that remaining space cannot fit other valuable items, leading to suboptimal total value.
In the Activity Selection Problem, n activities have start times $s_{i}$ and finish times $f_{i}$. Which greedy choice yields an optimal schedule with maximum non-overlapping activities?
Selecting the activity with the earliest finish time leaves the maximum possible remaining time for subsequent activities.
If activities in the Activity Selection Problem are already sorted by finish time $f_{i}$, what is the running time to find a maximum set of mutually compatible activities?
When input activities are pre-sorted by finish time, a single linear scan taking O(n) time selects compatible activities.